学步园

模板题。

//author: CHC
//First Edit Time:	2014-08-03 14:21
//Last Edit Time:	2014-08-03 14:21
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits.h>
using namespace std;
#define MAXN 10000  
#define MAXM 100000  
const int INF = INT_MAX;  
typedef long long LL;  
struct Edge  
{  
    int from,to,ci,next;  
    Edge(){}  
    Edge(int _from,int _to,int _ci,int _next):from(_from),to(_to),ci(_ci),next(_next){}  
}e[MAXM];  
int head[MAXN],tot;  
int dis[MAXN];  
int top,sta[MAXN],cur[MAXN];  
int n,m;  
inline void init(){  
    memset(head,-1,sizeof(head));  
    tot=0;  
}  
inline void AddEdge(int u,int v,int ci0,int ci1=0){  
    e[tot]=Edge(u,v,ci0,head[u]);  
    head[u]=tot++;  
    e[tot]=Edge(v,u,ci1,head[v]);  
    head[v]=tot++;  
}  
inline bool bfs(int st,int et){  
    memset(dis,0,sizeof(dis));  
    dis[st]=1;  
    queue <int> q;  
    q.push(st);  
    while(!q.empty()){  
        int now=q.front();  
        q.pop();  
        for(int i=head[now];i!=-1;i=e[i].next){  
            int next=e[i].to;  
            if(e[i].ci&&!dis[next]){  
                dis[next]=dis[now]+1;  
                if(next==et)return true;  
                q.push(next);  
            }  
        }  
    }  
    return false;  
}  
LL Dinic(int st,int et){  
    LL ans=0;  
    while(bfs(st,et)){  
        top=0;  
        memcpy(cur,head,sizeof(head));  
        int u=st,i;  
        while(1){  
            if(u==et){  
                int pos,minn=INF;  
                //printf("top:%d\n",top);  
                for(i=0;i<top;i++)  
                {  
                    if(minn>e[sta[i]].ci){  
                        minn=e[sta[i]].ci;  
                        pos=i;  
                    }  
                    //printf("%d --> %d\n",e[sta[i]].from,e[sta[i]].to);  
                }  
                for(i=0;i<top;i++){  
                    e[sta[i]].ci-=minn;  
                    e[sta[i]^1].ci+=minn;  
                }  
                top=pos;  
                u=e[sta[top]].from;  
                ans+=minn;  
                //printf("minn:%d\n\n",minn);  
            }  
            for(i=cur[u];i!=-1;cur[u]=i=e[i].next)  
                if(e[i].ci&&dis[u]+1==dis[e[i].to])break;  
            if(cur[u]!=-1){  
                sta[top++]=cur[u];  
                u=e[cur[u]].to;  
            }  
            else {  
                if(top==0)break;  
                dis[u]=0;  
                u=e[sta[--top]].from;  
            }  
        }  
    }  
    return ans;  
}  

int main()
{
    int n,m,t,cas=0;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        init();
        for(int i=0,x,y,ci;i<m;i++){
            scanf("%d%d%d",&x,&y,&ci);
            AddEdge(x,y,ci);
        }
        printf("Case %d: %I64d\n",++cas,Dinic(1,n));
    }
    return 0;
}