网络最大流

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define re register
 6 #define rep(i, a, b) for (re int i = a; i <= b; ++i)
 7 #define repd(i, a, b) for (re int i = a; i >= b; --i)
 8 #define maxx(a, b) a = max(a, b);
 9 #define minn(a, b) a = min(a, b);
10 #define LL long long
11 #define INF (1 << 30)
12 
13 inline int read() {
14     int w = 0, f = 1; char c = getchar();
15     while (!isdigit(c)) f = c == ‘-‘ ? -1 : f, c = getchar();
16     while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ ‘0‘), c = getchar();
17     return w * f;
18 }
19 
20 const int maxn = 1e4 + 5, maxm = 1e5 + 5;
21 
22 struct Edge {
23     int u, v, c, f, pre;
24 };
25 
26 struct Graph {
27     queue<int> Q;
28     Edge ed[maxm << 1];
29     int n, m, G[maxn], s, t;
30     void init(int n) {
31         this->n = n;
32         memset(G, 0, sizeof(G));
33         m = 1;
34     }
35     void add(int u, int v, int c) {
36         ed[++m] = (Edge){u, v, c, 0, G[u]};
37         G[u] = m;
38         ed[++m] = (Edge){v, u, 0, 0, G[v]};
39         G[v] = m;
40     }
41     int vis[maxn], d[maxn];
42     bool bfs() {
43         memset(vis, 0, sizeof(vis));
44         vis[s] = 1;
45         Q.push(s);
46         d[s] = 1;
47         while (!Q.empty()) {
48             int u = Q.front(); Q.pop();
49             for (register int i = G[u]; i; i = ed[i].pre) {
50                 Edge &e = ed[i];
51                 if (!vis[e.v] && ed[i].f < ed[i].c) {
52                     vis[e.v] = 1;
53                     Q.push(e.v);
54                     d[e.v] = d[u] + 1;
55                 }
56             }
57         }
58         return vis[t];
59     }
60     int cur[maxn];
61     int dfs(int u, int a) {
62         if (u == t || a == 0) return a;
63         int flow = 0, f;
64         for (register int &i = cur[u]; i; i = ed[i].pre) {
65             Edge &e = ed[i];
66             if (d[u] + 1 == d[e.v] && (f = dfs(e.v, min(a, e.c-e.f)))) {
67                 e.f += f;
68                 ed[i^1].f -= f;
69                 flow += f;
70                 a -= f;
71                 if (a == 0) break;
72             }
73         }
74         return flow;
75     }
76     int maxflow(int s, int t) {
77         this->s = s, this->t = t;
78         int flow = 0;
79         while (bfs()) {
80             rep(i, 1, n) cur[i] = G[i];
81             flow += dfs(s, INF);
82         }
83         return flow;
84     }
85 } G;
86 
87 int n, m, s, t;
88 
89 int main() {
90     n = read(), m = read(), s = read(), t = read();
91     G.init(n);
92     rep(i, 1, m) {
93         int u = read(), v = read(), c = read();
94         G.add(u, v, c);
95     }
96     printf("%d", G.maxflow(s, t));
97     return 0;
98 }