poj 1273 Drainage Ditches ( 最大流Edmonds_karp算法）

终于搞定了第一网络流的题~~看了好久啊才理解

题意：

   求排水沟的最大流量，最大流的模版题，EK算法

   若没听说过网络流，直接pass 吧.

  用g++提交 加上 string.h

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N =210;
const int inf =0x7fffffff;
int map[N][N],path[N],flow[N];
int start,end,m,n;
queue<int> q;
int bfs()
{
    while(!q.empty()) q.pop();
    memset(path,-1,sizeof(path));
    path[start]=0,flow[start]=inf;
    q.push(start);
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        if(t==end) break;
        for(int i=1;i<=m;i++)
        {
            if(i!=start&&path[i]==-1&&map[t][i])
            {
                flow[i]=flow[t]<map[t][i] ? flow[t]:map[t][i];
                q.push(i);
                path[i]=t;
            }
        }
    }
    if(path[m]==-1) return -1;
    return flow[m];
}

int Edmonds_karp()
{
    int now,pre,step,max_flow=0;
    while((step=bfs())!=-1)
    {
        now=end;max_flow+=step;
        while(now!=start)
        {
            pre=path[now];
            map[pre][now]-=step;
            map[now][pre]+=step;
            now=pre;
        }
    }
    return max_flow;
}
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        memset(map,0,sizeof(map));
        while(n--)
        {
            int u,v,cost;
            scanf("%d%d%d",&u,&v,&cost);
            map[u][v]+=cost;
        }
        start=1,end=m;
        printf("%d\n",Edmonds_karp());
    }
}

  

资料整理

维基百科+ 百度百科

简单清晰---FF
http://www.cppblog.com/mythit/archive/2011/12/30/80470.html

一刻钟二刻思
http://www.zhongsisi.com/maximum-flow-method-augmenting-path/

roba FF +EK  +距离标号
http://roba.ycool.com/post.1431010.html

算法总结参考
http://www.cppblog.com/guyuecanhui/articles/88393.html

ppt 资料搜集

http://www.ctdisk.com/shared/folder_985718_f0c85ff8/

题目：