网络流

 1const itn maxn = 1200 + 10;
 2const int maxe = 120000 + 10;
 3const ll inf = 1ll << 60;
 4
 5struct star{int to, next, w;};
 6int head[maxn], top = 0;
 7star edge[maxe << 1];
 8
 9void add(int u, int v, int w){
10    edge[top].to = v;
11    edge[top].next = head[u];
12    edge[top].w = w;
13    head[u] = top++;
14}
15
16int d[maxn], cur[maxn];
17
18ll dfs(int s, int t, ll flow){
19    if(flow == 0 || s == t) return flow;
20    
21    ll res = 0, f;
22    for(int i = cur[s]; ~i; i = edge[i].next){
23        cur[s] = i;
24        if(d[edge[i].to] == d[s] + 1){
25            f = dfs(edge[i].to, t, min(flow, (ll)edge[i].w));
26            edge[i].w -= f; edge[i ^ 1].w += f; res += f; flow -= f;
27            if(flow == 0) break;
28        }
29    }
30    return res;
31}
32
33queue<int> q, q0;
34bool bfs(int s, int t){
35    clr(d, 0);
36    q = q0; q.push(s);
37    cur[s] = head[s]; d[s] = 1;
38    while(!q.empty()){
39        int now = q.front(); q.pop();
40        for(int i = head[now]; ~i; i = edge[i].next) if(!d[edge[i].to] && edge[i].w > 0){
41            cur[edge[i].to] = head[edge[i].to]; d[edge[i].to] = d[now] + 1;
42            if(edge[i].to == t) return true;
43            q.push(edge[i].to);
44        }
45    }
46    return false;
47}
48
49ll dinic(int s, int t){
50    ll ans = 0;
51    while(bfs(s, t)) ans += dfs(s, t, inf);
52    return ans;
53}
54
55
56
57int main(){
58//    Fastin;
59    clr(head, -1);
60    int n, m, s, t; scanf("%d %d %d %d", &n, &m, &s, &t);
61    for(int i = 0, u, v, w; i < m; i++){
62        scanf("%d %d %d", &u, &v, &w);
63        add(u, v, w); add(v, u, 0);
64    }
65    printf("%lld\n", dinic(s, t));
66    return 0;
67}

 1const itn maxn = 1200 + 10;
 2const int maxe = 120000 + 10;
 3const ll inf = 1ll << 60;
 4
 5struct star{int to, next, w;};
 6int n, m, s, t;
 7int head[maxn], top = 0;
 8star edge[maxe << 1];
 9
10void add(int u, int v, int w){
11    edge[top].to = v;
12    edge[top].next = head[u];
13    edge[top].w = w;
14    head[u] = top++;
15}
16
17int d[maxn], cur[maxn], gap[maxn];
18
19queue<int> q;
20void bfs(int s, int t){
21    q.push(t); gap[d[t] = 1]++; cur[t] = head[t];
22    while(!q.empty()){
23        int now = q.front(); q.pop();
24        for(int i = head[now]; ~i; i = edge[i].next) if(!d[edge[i].to]){
25            gap[d[edge[i].to] = d[now] + 1]++;
26            cur[edge[i].to] = head[edge[i].to];
27            q.push(edge[i].to);
28        }
29    }
30}
31
32ll dfs(int x, int s, int t, ll flow){
33    if(x == t) return flow;
34    
35    ll res = 0, f;
36    for(int i = cur[x]; ~i; i = edge[i].next){
37        cur[x] = i;
38        if(d[x] == d[edge[i].to] + 1){
39            f = dfs(edge[i].to, s, t, min(flow, (ll)edge[i].w));
40            edge[i].w -= f; edge[i ^ 1].w += f; flow -= f; res += f;
41            if(flow == 0) return res;
42        }
43    }
44    if(!(gap[d[x]]--)) d[s] = n + 1;
45    gap[++d[x]]++; cur[x] = head[x];
46    return res;
47}
48
49ll isap(int s, int t){
50    bfs(s, t);
51    ll ans = dfs(s, s, t, inf);
52    while(d[s] <= n) ans += dfs(s, s, t, inf);
53    return ans;
54}
55
56int main(){
57//    Fastin;
58    clr(head, -1);
59    scanf("%d %d %d %d", &n, &m, &s, &t);
60    for(int i = 0, u, v, w; i < m; i++){
61        scanf("%d %d %d", &u, &v, &w);
62        add(u, v, w); add(v, u, 0);
63    }
64    printf("%lld\n", isap(s, t));
65    return 0;
66}