HDU 3549 Flow Problem(ネットワークフロー入門+テンプレート詳細)

転載は出典を明記してください.http://blog.csdn.net/a1dark
分析:最初のネットの流れの问题、EKアルゴリズムはとても良い感じがして、最初の时に反対の辺を追加して比较的に难しいことを除いてすべて比较的に理解しやすくて、よくなって、多く言わないで、どうせ1本の経典のネットの流入の门の问题はACにされて、更にいくつかの问题を切って更に効率的な予流の推进法を学び続けて、顽张ります!

#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
#define INF 0x7fffffff
#define MAXN 20
int map[MAXN][MAXN];
int vis[MAXN];
int pre[MAXN];//       
int m,n;
int bfs(int s,int t){
    queue<int > q;
    memset(pre,-1,sizeof(pre));
    memset(vis,0,sizeof(vis));
    pre[s]=s;
    vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=1;i<=n;i++){//          
            if(map[now][i]&&!vis[i]){
                pre[i]=now;//      、     
                vis[i]=1;
                if(i==t)return 1;//        
                q.push(i);
            }
        }
    }
    return 0;//       
}
int EK(int s,int t){
    int flow=0,d,i;
    while(bfs(s,t)){//            
        d=INF;
        for(i=t;i!=s;i=pre[i]){//        、        
            if(d>=map[pre[i]][i])
                d=map[pre[i]][i];
        }
        for(i=t;i!=s;i=pre[i]){//              、       
            map[pre[i]][i]-=d;
            map[i][pre[i]]+=d;//EK       、       、          
        }
        flow+=d;//      
    }
    return flow;
}
int main(){
    int t,k=1;
    scanf("%d",&t);
    while(t--){
        memset(map,0,sizeof(map));
        scanf("%d%d",&n,&m);
        int s,e,v;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&s,&e,&v);
            map[s][e]+=v;//       
        }
        printf("Case %d: %d
",k,EK(1,n));
        k++;
    }
    return 0;
}