P3376 【模板】网络最大流

P3376 【模板】网络最大流

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 10005, inf = 0x3f3f3f;
 4 struct Edge {
 5     int from, to, cap, flow;
 6 };
 7
 8 struct Dinic {
 9     int n, m, s, t;
10     vector<Edge> edges;
11     vector<int> G[maxn];
12     bool vis[maxn];
13     int d[maxn];
14     int cur[maxn];
15
16     void AddEdge(int from, int to, int cap) {
17         edges.push_back((Edge){from, to, cap, 0});
18         edges.push_back((Edge){to, from, 0, 0});
19         m = edges.size();
20         G[from].push_back(m-2);
21         G[to].push_back(m-1);
22     }
23     bool bfs() {
24         memset(vis, 0, sizeof(vis));
25         queue<int> que;
26         que.push(s);
27         d[s] = 0;
28         vis[s] = true;
29         while (!que.empty()) {
30             int x = que.front(); que.pop();
31             for (int i = 0; i < G[x].size(); ++i) {
32                 Edge& e = edges[G[x][i]];
33                 if (!vis[e.to] && e.cap > e.flow) {
34                     vis[e.to] = true;
35                     d[e.to] = d[x] + 1;
36                     que.push(e.to);
37                 }
38             }
39         }
40         return vis[t];
41     }
42     int dfs(int x, int a) {
43         if (x == t || a == 0) return a;
44         int flow = 0, f;
45         for (int& i = cur[x]; i < G[x].size(); ++i) {
46             Edge& e = edges[G[x][i]];
47             if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap-e.flow))) > 0) {
48                 e.flow += f;
49                 edges[G[x][i]^1].flow -= f;
50                 flow += f;
51                 a -= f;
52                 if (a == 0) break;
53             }
54         }
55         return flow;
56     }
57     int maxflow(int s, int t) {
58         this->s = s; this->t = t;
59         int flow = 0;
60         while (bfs()) {
61             memset(cur,0,sizeof(cur));
62             flow += dfs(s,inf);
63         }
64         return flow;
65     }
66 }dinic;
67 int main() {
68     int n, m, s, t; scanf("%d%d%d%d",&n,&m,&s,&t);
69     for (int i = 1; i <= m; ++i) {
70         int u, v, w; scanf("%d%d%d",&u,&v,&w);
71         dinic.AddEdge(u,v,w);
72     }
73     int ans = dinic.maxflow(s,t);
74     printf("%d\n",ans);
75     return 0;
76 }