题目:给出一个网络图,以及其源点和汇点,求出其网络最大流。
解法:网络流Dinic算法。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<queue>
6 using namespace std;
7
8 const int N=10010,M=100010,INF=(int)1e9;
9 int n,m,st,ed,len=1;
10 int last[N],d[N];
11 struct edge{int y,fl,next;}a[2*M];
12 queue<int> q;
13
14 int mmin(int x,int y) {return x<y?x:y;}
15 void ins(int x,int y,int fl)
16 {
17 a[++len].y=y,a[len].fl=fl;
18 a[len].next=last[x],last[x]=len;
19 a[++len].y=x,a[len].fl=0;
20 a[len].next=last[y],last[y]=len;
21 }
22 bool bfs()
23 {
24 while (!q.empty()) q.pop();
25 memset(d,-1,sizeof(d));
26 q.push(st); d[st]=1;
27 while (!q.empty())
28 {
29 int x=q.front(); q.pop();
30 for (int i=last[x];i!=-1;i=a[i].next)
31 {
32 int y=a[i].y;
33 if (!a[i].fl || d[y]!=-1) continue;
34 d[y]=d[x]+1; q.push(y);
35 }
36 }
37 return (d[ed]!=-1);
38 }
39 int dfs(int x,int flow)
40 {
41 if (x==ed) return flow;
42 int sum=0;
43 for (int i=last[x];i!=-1;i=a[i].next)
44 {
45 int y=a[i].y;
46 if (d[y]!=d[x]+1 || !a[i].fl) continue;
47 int p=mmin(a[i].fl,flow-sum);
48 int tmp=dfs(y,p);
49 sum+=tmp;
50 a[i].fl-=tmp,a[i^1].fl+=tmp;
51 if (sum==flow) break;
52 }
53 if (!sum) d[x]=-1;
54 return sum;
55 }
56 int Max_flow()
57 {
58 int sum=0,p;
59 while (bfs())
60 while (p=dfs(st,INF)) sum+=p;
61 return sum;
62 }
63 int main()
64 {
65 scanf("%d%d%d%d",&n,&m,&st,&ed);
66 int x,y,d;
67 memset(last,-1,sizeof(last));
68 for (int i=1;i<=m;i++)
69 {
70 scanf("%d%d%d",&x,&y,&d);
71 ins(x,y,d);
72 }
73 printf("%d\n",Max_flow());
74 return 0;
75 }