洛谷 P2740 [USACO4.2]草地排水Drainage Ditches

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<cstring>
 7 using namespace std;
 8 
 9 const int maxn=210;
10 const int inf=0x7f;
11 
12 int n,m;
13 int u,v,w;
14 int G[maxn][maxn];
15 int dis[210];
16 int cur[210];
17 queue<int> q;
18 
19 bool bfs() {
20     memset(dis,-1,sizeof(dis));
21     while (!q.empty()) q.pop();
22     dis[1]=0;
23     q.push(1);
24     while (!q.empty()) {
25         int x=q.front();
26         q.pop();
27         for (int i=1; i<=m; ++i) {
28             if (dis[i]==-1&&G[x][i]>0) {
29                 dis[i]=dis[x]+1;
30                 if(i==m) return true;
31                 q.push((i));
32             }
33         }
34     }
35     return false;
36 }
37 
38 
39 int dfs(int x,int a) {
40     if (x==m) return a;
41     int f=0,i;
42     for (i=1; i<=m; ++i) {
43         if(dis[i]==dis[x]+1&&G[x][i]>0&&(f=dfs(i,min(a,G[x][i])))) {
44             G[x][i]-=f;
45             G[i][x]+=f;
46             return f;
47         }
48     }
49     return false;
50 }
51 
52 
53 
54 int max_flow() {
55     int flow=0;
56     while (bfs()) flow+=dfs(1,inf);
57     return flow;
58 }
59 
60 int main() {
61     scanf("%d%d",&n,&m);
62     for (int i=1; i<=n; ++i) {
63         scanf("%d%d%d",&u,&v,&w);
64         G[u][v]+=w;
65     }
66     cout<<max_flow();
67     return 0;
68 }