POJ-1273-Drainage Ditches（网络流之最大流）

 1 #include<algorithm>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #define N 205
 7 #define MAX 1e8
 8 using namespace std;
 9 int n,m,x,y,z,tot,ans,fee,Min;
10 int head[N],level[N];
11 struct node{
12     int next,to,fee;
13 }e[2*N];
14 void add(int x,int y,int z){
15     e[tot].next=head[x];
16     head[x]=tot;
17     e[tot].to=y;
18     e[tot].fee=z;
19     tot++;
20     e[tot].next=head[y];
21     head[y]=tot;
22     e[tot].to=x;
23     e[tot].fee=0;
24     tot++;
25 }
26 queue<int> q;
27 bool bfs(int s,int t){
28     memset(level,0,sizeof(level));
29     level[s]=1;
30     while (!q.empty()) q.pop();
31     q.push(s);
32     while (!q.empty()){
33         int k=q.front();
34         q.pop();
35         if (k==t) return true;
36         for (int i=head[k];i!=-1;i=e[i].next){
37             int v=e[i].to;
38             if (e[i].fee&&!level[v]){
39                 level[v]=level[k]+1;
40                 q.push(v);
41             }
42         }
43     }
44     return false;
45 }
46 int dfs(int s,int maxf,int t){
47     if (s==t) return maxf;
48     int ret=0;
49     for (int i=head[s];i!=-1;i=e[i].next){
50         int v=e[i].to;
51         fee=e[i].fee;
52         if (level[v]==level[s]+1){
53             Min=min(maxf-ret,fee);
54             fee=dfs(v,Min,t);
55             e[i].fee-=fee;
56             e[i^1].fee+=fee;
57             ret+=fee;
58             if (ret==maxf) return ret; 
59         }
60     }
61     return ret;
62 }
63 int Dinic(int s,int t){
64     ans=0;
65     while (bfs(s,t)) ans+=dfs(s,MAX,t);
66     return ans;
67 }
68 int main(){
69     while (~scanf("%d%d",&n,&m)){
70         tot=0;
71         memset(head,-1,sizeof(head));
72         for (int i=1;i<=n;i++)
73             scanf("%d%d%d",&x,&y,&z),add(x,y,z);
74         printf("%d\n",Dinic(1,m));
75     }
76     return 0;
77 }