ACM模板——网络流

 1 #include<bits/stdc++.h>
 2 #define _for(i,a,b) for(register int i = (a);i < b;i ++)
 3 #define _rep(i,a,b) for(register int i = (a);i > b;i --)
 4 #define INF 0x3f3f3f3f
 5 #define MOD 100000000
 6 #define maxn 1000003
 7 #define pb push_back
 8 #define debug() printf("Miku Check OK!\n")
 9 typedef long long ll;
10 
11 using namespace std;
12 typedef pair<int,int> P;
13 inline ll read()
14 {
15     ll ans = 0;
16     char ch = getchar(), last = ‘ ‘;
17     while(!isdigit(ch)) last = ch, ch = getchar();
18     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - ‘0‘, ch = getchar();
19     if(last == ‘-‘) ans = -ans;
20     return ans;
21 }
22 inline void write(ll x)
23 {
24     if(x < 0) x = -x, putchar(‘-‘);
25     if(x >= 10) write(x / 10);
26     putchar(x % 10 + ‘0‘);
27 }
28 int ver[maxn],Next[maxn],head[maxn],val[maxn];
29 //incf[i]为i在此趟BFS流过的流量 
30 int vis[maxn],incf[maxn],pre[maxn];
31 int n,m,s,t,tot,maxflow;
32 void add(int x,int y,int w)
33 {
34     ver[++tot] = y,Next[tot] = head[x],head[x] = tot,val[tot] = w;
35 }
36 bool bfs()
37 {
38     memset(vis,0,sizeof(vis));
39     queue<int> q;
40     q.push(s);vis[s] = 1;
41     incf[s] = INF;
42     while(!q.empty())
43     {
44         int x = q.front();q.pop();
45         for(int i = head[x]; i; i = Next[i])
46             if(val[i])
47             {
48                 int y = ver[i];
49                 if(vis[y]) continue;
50                 incf[y] = min(incf[x],val[i]);
51                 pre[y] = i;
52                 q.push(y);vis[y] = 1;
53                 if(y==t) return true;
54             }
55         
56     }
57     return false;
58 }
59 void update()
60 {
61     int x = t;
62     while(x != s)
63     {
64         int i = pre[x];
65         val[i] -= incf[t];
66         val[i^1] += incf[t];
67         x = ver[i^1];
68         
69     }
70     maxflow += incf[t];
71 }
72 int main()
73 {
74     n = read();m = read();s = read();t = read();
75     tot = 1;maxflow = 0;
76     _for(i,1,m+1)
77     {
78         int x = read();int y = read();int c = read();
79         add(x,y,c);add(y,x,0);
80     } 
81     while(bfs()) update();
82     write(maxflow);
83     return 0;
84 }