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; 
}