1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<iostream> 5 #include<queue> 6 #define eps 0.000001 7 #define MAXN 20 8 #define MAXM 2005 9 #define INF (1<<30)10 using namespace std;11 int i,j,k,n,m,x,y,T,head[MAXN],num,w,pre[MAXN],lin[MAXN];12 struct edgenode13 {14     int to,next,w;15 } map[MAXM];16 17 void add_edge(int id,int x,int y,int w)18 {19     map[id].to=y;20     map[id].w=w;21     map[id].next=head[x];22     head[x]=id;23 }24 25 bool bfs(int s,int t)26 {27     int u,v;28     queue <int> q;29     memset(pre,-1,sizeof(pre));30     pre[s]=s;31     q.push(s);32     while(!q.empty())33     {34         u=q.front();35         q.pop();36         for(int i=head[u];i!=-1;i=map[i].next)37         {38             v=map[i].to;39             if(pre[v]==-1&&map[i].w>0)40             {41                 pre[v]=u;42                 lin[v]=i;43                 if (v==t) return true;44                 q.push(v);45             }46         }47     }48     return false;49 }50 51 int Edmonds_Karp(int s,int t)52 {53     int flow=0,d,i;54     while(bfs(s,t))55     {56         d=INF;57         for(i=t;i!=s;i=pre[i])58             d=min(d,map[lin[i]].w);59         for(i=t;i!=s;i=pre[i])60         {61             map[lin[i]].w-=d;62             map[lin[i]^1].w+=d;63         }64         flow+=d;65     }66     return flow;67 }68 69 void init()70 {71     memset(head,-1,sizeof(head));72     scanf("%d%d",&n,&m);73     num=0;74     for (i=0;i<m;i++)75     {76         scanf("%d%d%d",&x,&y,&w);77         add_edge(i*2,x,y,w);78         add_edge(i*2+1,y,x,0);79     }80 }81 82 int main()83 {84     scanf("%d",&T);85     for (int cas=1;cas<=T;cas++)86     {87         init();88         printf("Case %d: %d\n",cas,Edmonds_Karp(1,n));89     }90 }