网络流--Dinic(自用，勿看)

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<vector>
 5 #include<queue>
 6 using namespace std;
 7 #define fi first
 8 #define se second
 9 #define mp make_pair
10 #define pb push_back
11 typedef long long ll;
12 typedef unsigned long long ull;
13 typedef pair<int,int> pii;
14 namespace F
15 {
16 
17 struct E
18 {
19     int to,nxt,from,cap,flow;
20 }e[200100];
21 int f1[10100],ne=1;
22 int S,T,n;
23 int d[10100];
24 bool bfs()
25 {
26     int k,u;
27     memset(d,0,sizeof(int)*(n+1));
28     queue<int> q;
29     q.push(S);d[S]=1;
30     while(!q.empty())
31     {
32         u=q.front();q.pop();
33         for(k=f1[u];k;k=e[k].nxt)
34             if(!d[e[k].to]&&e[k].cap>e[k].flow)
35             {
36                 d[e[k].to]=d[u]+1;
37                 //if(e[k].to==T)    return 1;
38                 q.push(e[k].to);
39             }
40     }
41     //return 0;
42     return d[T];
43 }
44 int cur[10100];
45 int dfs(int u,int x)
46 {
47     if(u==T||x==0)    return x;
48     int flow=0,f;
49     for(int &k=cur[u];k;k=e[k].nxt)
50         if(e[k].cap>e[k].flow&&d[e[k].to]==d[u]+1)
51         {
52             f=dfs(e[k].to,min(x-flow,e[k].cap-e[k].flow));
53             e[k].flow+=f;e[k^1].flow-=f;flow+=f;
54             if(flow==x)    return flow;
55         }
56     return flow;
57 }
58 int solve()
59 {
60     int flow=0;
61     while(bfs())
62     {
63         memcpy(cur,f1,sizeof(int)*(n+1));
64         flow+=dfs(S,0x3f3f3f3f);
65     }
66     return flow;
67 }
68 void me(int a,int b,int c)
69 {
70     e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;
71     e[ne].from=a;e[ne].cap=c;
72     e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;
73     e[ne].from=b;e[ne].cap=0;
74 }
75 
76 }
77 int n,m;
78 int main()
79 {
80     int i,a,b,c;
81     scanf("%d%d%d%d",&n,&m,&F::S,&F::T);F::n=n;
82     for(i=1;i<=m;i++)
83     {
84         scanf("%d%d%d",&a,&b,&c);
85         F::me(a,b,c);
86     }
87     printf("%d",F::solve());
88     return 0;
89 }