1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <queue>
  6 using namespace std;
  7 #define pb push_back
  8 
  9 const int N = 1e4 + 10;
 10 const int M = 1e5 + 10;
 11 const int INF = 2e9;
 12 struct edge{
 13     int to, nxt, flow;
 14 }e[M << 1];
 15 int head[N], d[N], cur[N];
 16 queue<int > que;
 17 int n, m, s, t, tot;
 18 
 19 //dinic算法 复杂度O(n^2*m) 二部图时O(n^0.5*m)
 20 //bfs分层  增广路只能从上一层走到下一层
 21 //dfs求流  得到该增广路的最小允许流
 22 
 23 inline void add(int u, int v, int flow){
 24     e[tot].to = v; e[tot].flow = flow;
 25     e[tot].nxt = head[u]; head[u] = tot++;
 26     e[tot].to = u; e[tot].flow = 0;
 27     e[tot].nxt = head[v]; head[v] = tot++;
 28 }
 29 
 30 inline void init(){
 31     for(int i = 1; i <= n; ++i) cur[i] = head[i];
 32     while(!que.empty()) que.pop();
 33     for(int i = 1; i <= n; ++i) d[i] = 0;
 34 }
 35 
 36 bool bfs(int s, int t){
 37     d[s] = 1;
 38     que.push(s);
 39     int to, flow;
 40     while(!que.empty()){
 41         int now = que.front();
 42         que.pop();
 43         for(int o = head[now]; ~o; o = e[o].nxt){
 44             to = e[o].to;
 45             flow = e[o].flow;
 46             if(!d[to] && flow){
 47                 d[to] = d[now] + 1;
 48                 que.push(to);
 49             }
 50         }
 51     }
 52     if(d[t]) return true;
 53     else return false;
 54 }
 55 
 56 int dfs(int now, int t, int F){
 57     if(now == t) return F;
 58 
 59     int sum = 0;
 60     int to, flow, tmp;
 61     //当前弧优化,因为是dfs,如果遍历了当前边,当它使用之后,之后再用到这个边很大概率效果也是和之前一样,减少了一些时间开销
 62     for(int& o = cur[now]; ~o; o = e[o].nxt){
 63         to = e[o].to;
 64         flow = e[o].flow;
 65         if(flow && d[to] == d[now] + 1){
 66             tmp = dfs(to, t, min(F - sum, flow));
 67 
 68             //没有流  则不更新
 69             if(!tmp) continue;
 70             e[o].flow -= tmp; e[o^1].flow += tmp;
 71             sum += tmp;
 72             if(sum == F) return sum;
 73         }
 74     }
 75 
 76     return sum;
 77 }
 78 
 79 void dinic(int s,int& sum_flow){
 80     for(int i = 1; i <= n; ++i) cur[i] = head[i];
 81     while(bfs(s, t)){
 82         sum_flow += dfs(s, t, INF);
 83         init();
 84     }
 85 }
 86 
 87 void solve(){
 88 
 89     while(~scanf("%d%d%d%d", &n, &m, &s, &t)){
 90         int u, v, w;
 91         for(int i = 1; i <= n; ++i) head[i] = -1; tot = 0;
 92         for(int i = 1; i <= m; ++i){
 93             scanf("%d%d%d", &u, &v, &w);
 94             add(u, v, w);
 95         }
 96         int sum_flow = 0;
 97         dinic(s, sum_flow);
 98         //printf("sum_flow = %d\n", sum_flow);
 99         printf("%d\n", sum_flow);
100     }
101 }
102 
103 int main(){
104 
105     solve();
106 
107     return 0;
108 }

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。