网络流—最大流

因为开学了，感觉自己懒了很多，很久都没有写博客了。是时候改变一下自己了

今天学了一下网络流的最大流,做了一下水题，慢慢找回感觉，继续ACM

 1 /*HDU 3549*/
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <queue>
 5 #include <algorithm>
 6 #include <string.h>
 7 using namespace std;
 8 const int maxm = 20;
 9 int n,m;
10 int map[maxm][maxm];
11 bool vis[maxm];
12 int pre[maxm];
13 bool bfs(int s,int t){
14     memset(vis,0,sizeof(vis));
15     memset(pre,0,sizeof(pre));
16     queue<int> q;
17     q.push(s);
18     vis[s]=1;
19     pre[s]=s;
20     while(!q.empty()){
21         int p=q.front();
22         q.pop();
23         for(int i=1;i<=n;i++){
24             if(map[p][i]>0&&!vis[i]){
25                 vis[i]=1;
26                 pre[i]=p;
27                 if(i==t)return true;
28                 q.push(i);
29             }
30         }
31     }
32     return false;
33 
34 }
35 int EK(int s,int t){
36     int maxd=0,d;
37     while(bfs(s,t)){
38         d=1<<30;
39         for(int i=t;i!=s;i=pre[i])d=min(d,map[pre[i]][i]);
40         for(int i=t;i!=s;i=pre[i]){
41             map[pre[i]][i]-=d;
42             map[i][pre[i]]+=d;
43         }
44         maxd+=d;
45     }
46     return maxd;
47 }
48 int main(){
49     int t;
50     scanf("%d",&t);
51     for(int j=1;j<=t;j++){
52         scanf("%d%d",&n,&m);
53         memset(map,0,sizeof(map));
54         int u,v,w;
55         for(int i=0;i<m;i++){
56             scanf("%d%d%d",&u,&v,&w);
57             map[u][v]+=w;
58         }
59         printf("Case %d: %d
",j,EK(1,n));
60     }
61     return 0 ;
62 }