【洛谷P2936】全流

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 using namespace std;
 6 const int INF=99999999;
 7 queue<int>q;
 8 int n,w[257][257],d[257];
 9 inline bool bfs()
10 {
11     memset(d,0,sizeof(d));
12     d[‘A‘]=1;
13     q.push(‘A‘);
14     while(!q.empty())
15     {
16         int now=q.front();
17         q.pop();
18         for(int i=‘A‘;i<=‘z‘;i++)   //一定要到小写z
19             if(w[now][i]>0&&d[i]==0)
20             {
21                 d[i]=d[now]+1;
22                 q.push(i);
23             }
24     }
25     return d[‘Z‘]!=0;
26 }
27 int dfs(int now,int dist)
28 {
29     if(now==‘Z‘) return dist;
30     for(int i=‘A‘;i<=‘z‘;i++)  //同上
31         if(d[i]==d[now]+1&&w[now][i]>0)
32         {
33             int x=dfs(i,min(dist,w[now][i]));
34             if(x>0)
35             {
36                 w[now][i]-=x;
37                 w[i][now]+=x;
38                 return x;
39             }
40         }
41     return 0;
42 }
43 int main()
44 {
45     cin>>n;
46     for(int i=1;i<=n;i++)
47     {
48         char x,y;
49         int z;
50         cin>>x>>y>>z;
51         w[x][y]+=z;
52     }
53     int ans=0;
54     while(bfs())
55     {
56         while(int di=dfs(‘A‘,INF))
57             ans+=di;
58     }
59     cout<<ans;
60     return 0;
61 }