网络流之最大流Dinic算法模版

 1 /*
 2 网络流之最大流Dinic算法模版
 3  */
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <queue>
 7 using namespace std;
 8 const int maxn = 205;
 9 const int inf = 0x3f3f3f3f;
10 struct
11 {
12     int c,f;//c为边的容量，f为边的容量
13 }edge[maxn][maxn];
14 int dis[maxn];
15 int v,e;
16 bool bfs()//利用bfs进行分层处理，当汇点无法分层时得到最大流
17 {
18     memset(dis,0,sizeof dis);
19     queue<int> q;
20     q.push(1);
21     dis[1] = 1;
22     while(!q.empty())
23     {
24         int u = q.front(); q.pop();
25         for(int i = 1; i <= v; ++i)
26             if(!dis[i] && edge[u][i].c > edge[u][i].f)
27             {dis[i] = dis[u] + 1;q.push(i);}
28     }
29     return dis[v] != 0;
30 }
31 int dfs(int u,int c)//增广
32 {
33     if(u == v) return c;
34     int temp = c;
35     for(int i = 1; i <= v && temp; ++i)
36     {
37         if(dis[i] != dis[u] + 1 || edge[u][i].c <= edge[u][i].f) continue;
38         int t = dfs(i,min(temp,edge[u][i].c - edge[u][i].f));
39         edge[u][i].f += t; edge[i][u].f -= t; temp -= t;
40     }
41     return c - temp;
42 }
43 int dinic()
44 {
45     int ans = 0;
46     while(bfs())
47         while(int t = dfs(1,inf))
48             ans += t;
49     return ans;
50 }
51 int main()
52 {
53     while(~scanf("%d%d",&e,&v))
54     {
55         memset(edge,0,sizeof edge);
56         while(e--)
57         {
58             int x,y,z;
59             scanf("%d%d%d",&x,&y,&z);
60             edge[x][y].c += z;
61         }
62         int ans = dinic();
63         printf("%d
",ans);
64     }
65     return 0;
66 }