poj1273 Drainage Ditches （最大流模板）

http://poj.org/problem?id=1273

Dinic算法

这是一道最大流的经典题

最大流尽量应该用边表，优于邻接矩阵（所以我写了邻接矩阵版的之后又写了个边表）

用了新学的Dinic算法

在每次找增广路之前先跑一遍bfs，把所有点的深度标记，按bfs记下的顺序找增广路，这条增广路上最小的边容量就是这条增广路的最大费用

跑出一条增广路之后，就开始更新现在的边剩余的容量，并建立反向边。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m,map[300][300],ans,pre[300];
void Flow(int s,int t){
    while(1){
        queue<int>q;
        q.push(1);
        memset(pre,0,sizeof(pre));
        while(!q.empty()){
            int point=q.front();
            q.pop();if(point==t)break;
            for(int i=1;i<=n;i++){
                if(map[point][i]&&!pre[i])pre[i]=point,q.push(i);
            }
        }if(pre[t]==0)break;
        int so=0x7fffffff;
        for(int i=t;i!=s;i=pre[i]){
            so=min(so,map[pre[i]][i]);
        }ans+=so;
        for(int i=t;i!=s;i=pre[i]){
            map[i][pre[i]]+=so;
            map[pre[i]][i]-=so;
        }
    }
}
int main(){
    while(scanf("%d%d",&m,&n)!=EOF){
        int f,t,v;
        memset(map,0,sizeof(map));
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&f,&t,&v);
            map[f][t]+=v;
        }
        ans=0;
        Flow(1,n);
        printf("%d
",ans);
    }
}