1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<stdlib.h>

 4 #include<iostream>

 5 #include<string.h>

 6 #include<math.h>

 7 #include<vector>

 8 #include<map>

 9 #include<queue>

10 struct pp

11 {

12     int x;

13     int cap;

14     int pre;

15 };

16 const int N=1e8;

17 bool used[30];

18 using namespace std;

19 vector<pp>GG[30];

20 void add(int from,int to,int vv)

21 {   pp ss;

22     ss.cap=vv;ss.x=to;ss.pre=GG[to].size();

23     GG[from].push_back(ss);

24     ss.cap=0;ss.x=from;ss.pre=GG[from].size()-1;

25     GG[to].push_back(ss);

26 }

27 int dfs(int x,int y,int co)

28 {

29     if(x==y)

30     {

31         return co;

32     }

33     used[x]=true;

34     int i,j;

35     for(i=0;i<GG[x].size();i++)

36     {  int cc ;

37         pp &LL=GG[x][i];

38         if(!used[LL.x]&&LL.cap>0)

39         {

40              cc=dfs(LL.x,y,min(co,LL.cap));

41             if(cc>0)

42             {

43                 LL.cap-=cc;

44                 GG[LL.x][LL.pre].cap+=cc;

45                 return cc;

46             }

47         }

48     }

49     return 0;

50 }

51 int max_flow(int x,int t)

52 {

53     int flow=0;

54     while(1)

55     {memset(used,0,sizeof(used));

56         int kk=dfs(x,t,N);

57         if(kk==0)

58         {

59             return flow;

60         }

61         else flow+=kk;

62     }

63

64 }

65 int main(void)

66 {

67     int i,j,k,p,q;

68     scanf("%d",&k);

69

70     for(i=1;i<=k;i++)

71     { for(j=0;j<30;j++)

72        GG[j].clear();

73         scanf("%d %d",&p,&q);

74         int x;int y;int n,m;

75         for(j=0;j<q;j++)

76         {

77             scanf("%d %d %d",&x,&y,&n);

78             add(x,y,n);

79         }

80         int M=max_flow(1,p);

81         printf("Case %d: %d\n",i,M);

82     }

83     return 0;

84 }

  1 #include<stdio.h>

  2 #include<algorithm>

  3 #include<stdlib.h>

  4 #include<iostream>

  5 #include<string.h>

  6 #include<math.h>

  7 #include<vector>

  8 #include<map>

  9 #include<queue>

 10 using namespace std;

 11 struct node

 12 {

 13         int to;

 14         int cap;

 15         int rev;

 16 };

 17 int level[20];

 18 int iter[20];

 19 vector<node>vec[20];

 20 void add_edge(int from,int to,int cap )

 21 {

 22         vec[from].push_back(node {to,cap,vec[to].size()});

 23         vec[to].push_back(node {from,0,vec[from].size()-1});

 24 }

 25 void BFS(int s);

 26 int dfs(int id,int t,int f );

 27 int max_flow(int s,int t);

 28 const int N=1e9;

 29 int main(void)

 30 {

 31         int i,j,k,p,q;

 32         int x,y;

 33         scanf("%d",&k);

 34         int s;

 35         for(s=1; s<=k; s++)

 36         {

 37                 scanf("%d %d",&p,&q);

 38                 for(i=0;i<20;i++)

 39                 {

 40                     vec[i].clear();

 41                 }

 42                 for(i=0; i<q; i++)

 43                 {

 44                         int z;

 45                         scanf("%d %d %d",&x,&y,&z);

 46                         add_edge(x,y,z);

 47                 }

 48                 int sum=max_flow(1,p);

 49                 printf("Case %d: ",s);

 50                 printf("%d\n",sum);

 51         }

 52         return 0;

 53 }

 54 void BFS(int s)

 55 {

 56         memset(level,-1,sizeof(level));

 57         queue<int>que;

 58         level[s]=0;

 59         que.push(s);

 60         while(!que.empty())

 61         {

 62                 int id=que.front();

 63                 que.pop();

 64                 for(int i=0; i<vec[id].size(); i++)

 65                 {

 66                         node x=vec[id][i];

 67                         if(level[x.to]<0&&x.cap>0)

 68                         {

 69                                 level[x.to]=level[id]+1;

 70                                 que.push(x.to);

 71                         }

 72                 }

 73         }

 74 }

 75 int dfs(int id,int t,int f )

 76 {

 77         if(t==id)return f;

 78         for(int &i=iter[id]; i<vec[id].size(); i++)

 79         {

 80                 node &vv=vec[id][i];

 81                 if(level[vv.to]>level[id]&&vv.cap>0)

 82                 {

 83                         int d=dfs(vv.to,t,min(f,vv.cap));

 84                         if(d>0)

 85                         {

 86                                 vv.cap-=d;

 87                                 vec[vv.to][vv.rev].cap+=d;

 88                                 return d;

 89                         }

 90                 }

 91         }

 92         return 0;

 93 }

 94 int max_flow(int s,int t)

 95 {

 96         int flow=0;

 97        for(;;)

 98         {

 99                 BFS(s);

100                 if(level[t]<0)

101                 {

102                         return flow;

103                 }

104                 int f=0;

105                 memset(iter,0,sizeof(iter));

106                 while( (f=dfs(s,t,N))>0)

107                 {

108                 if(f==0)break;

109                         flow+=f;

110                 }

111         }

112 }