hdu 1532 EK求最大流

今天晚上开始接触网络流，终于算是搞懂了EK这一个算法，不过肯定还需要多刷题巩固。

EK应该是最朴素的求最大流的算法了。大概的思路就是用bfs找增广路，然后每找到一条就将它最大程度扩大流量，也就是加上最小残量，将这条路径状态改变。直到找不到增光路，说明此时已经是最大流。

EK效率太低。继续学习其他网络流的算法。

关于网络流，算法导论上讲的很详细。基础知识网上也有资料。

此题代码和思路：

[cpp]
//EK求最大流
#include<stdio.h>
#include<string.h>
const int MAX=250,INF=0x7FFFFFFF;
int map[MAX][MAX],flow[MAX][MAX],minf[MAX],q[MAX],fa[MAX];
int main()
{
// freopen("in.txt","r",stdin);
    int i,n,m,a,b,c;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(map,0,sizeof(map));
        memset(flow,0,sizeof(flow));
        int max_flow=0;
        for(i=0;i<n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            map[a][b]+=c;       //建图，注意可能存在平行边
        }
        while(1)
        {
            int re=0,fr=0,u,k;
            memset(q,0,sizeof(q));
            memset(minf,0,sizeof(minf));
            memset(fa,0,sizeof(fa));
            q[re++]=1;
            minf[1]=INF;
            while(fr<re)         //BFS找增广路
            {
                u=q[fr++];
                for(k=1;k<=m;k++)
                    if(!minf[k]&&map[u][k]>flow[u][k])
                    {
                        q[re++]=k;
                        fa[k]=u;
                        int ad=map[u][k]-flow[u][k];
                        minf[k]=minf[u]<ad?minf[u]:ad; //记录最小残余量
                    }
            }
            if(!minf[m]) break;         //没有更新最小残余量，说明无增广路
            for(k=m;k!=1;k=fa[k])       //更新路径状态
            {
                flow[fa[k]][k]+=minf[m];
                flow[k][fa[k]]-=minf[m];
            }
            max_flow+=minf[m];     //更新总流量
        }
        printf("%d\n",max_flow);
    }
    return 0;
}

补充：软件开发 , C++ ,