如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。
输入格式:
第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数ui、vi、wi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi)
输出格式:
一行,包含一个正整数,即为该网络的最大流。
输入样例#1:
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40
输出样例#1:
50
时空限制:1000ms,128M
数据规模:
对于30%的数据:N<=10,M<=25
对于70%的数据:N<=200,M<=1000
对于100%的数据:N<=10000,M<=100000
样例说明:
题目中存在3条路径:
4-->2-->3,该路线可通过20的流量
4-->3,可通过20的流量
4-->2-->1-->3,可通过10的流量(边4-->2之前已经耗费了20的流量)
故流量总计20+20+10=50。输出50。
看了几本教材发现都没有用边表去写网络流的,于是自己琢磨了很长时间,
用的是Dinic算法
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #include<algorithm>
7 #define lli long long int
8 using namespace std;
9 const int MAXN=300001;
10 const int maxn=0x7fffff;
11 void read(int &n)
12 {
13 char c='+';int x=0;bool flag=0;
14 while(c<'0'||c>'9')
15 {c=getchar();if(c=='-')flag=1;}
16 while(c>='0'&&c<='9')
17 {x=x*10+c-48;c=getchar();}
18 flag==1?n=-x:n=x;
19 }
20 struct node
21 {
22 int u,v,flow,cap,nxt;
23 }edge[MAXN];
24 int head[MAXN];
25 int num=0;
26 int n,m,S,T;
27 int dis[MAXN];
28 int vis[MAXN];
29 int cur[MAXN];
30 void add_edge(int x,int y,int z)
31 {
32 edge[num].u=x;
33 edge[num].v=y;
34 edge[num].cap=z;
35 edge[num].flow=0;
36 edge[num].nxt=head[x];
37 head[x]=num++;
38 }
39 bool bfs(int bg,int ed)
40 {
41 memset(dis,-1,sizeof(dis));
42 queue<int>q;
43 q.push(bg);
44 dis[bg]=0;
45 while(!q.empty())
46 {
47 int p=q.front();
48 q.pop();
49 for(int i=head[p];i!=-1;i=edge[i].nxt)
50 {
51 if(dis[edge[i].v]==-1&&edge[i].cap>edge[i].flow)
52 {
53 vis[edge[i].v]=1;
54 dis[edge[i].v]=dis[edge[i].u]+1;
55 q.push(edge[i].v);
56 }
57 }
58 }
59 if(dis[ed]==-1)
60 return 0;
61 else return 1;
62 }
63 int dfs(int now,int a)// a:所有弧的最小残量
64 {
65 if(now==T||a<=0)
66 return a;
67
68 int flow=0,f;
69 for(int i=head[now];i!=-1;i=edge[i].nxt)
70 {
71 if(dis[now]+1==dis[edge[i].v]&&edge[i].cap-edge[i].flow>0)
72 {
73 f=dfs(edge[i].v,min(a,edge[i].cap-edge[i].flow));
74 edge[i].flow+=f;
75 edge[i^1].flow-=f;
76 flow+=f;
77 a-=f;
78 if(a<=0)break;
79 }
80 }
81 return flow;
82 }
83 void Dinic(int S,int T)
84 {
85 int ansflow=0;
86 for(int i=1;i<=n;i++)
87 cur[i]=head[i];
88 while(bfs(S,T))// 求出层级
89 ansflow+=dfs(S,maxn);
90 printf("%d",ansflow);
91
92 }
93 int main()
94 {
95 read(n);read(m);
96 // swap(n,m);
97 // S=1;T=m;
98 read(S);read(T);
99 for(int i=1;i<=n;i++)
100 head[i]=-1;
101 for(int i=1;i<=m;i++)
102 {
103 int x,y,z;
104 read(x);read(y);read(z);
105 add_edge(x,y,z);
106 add_edge(y,x,0);
107 }
108 Dinic(S,T);
109 return 0;
110 }
update in 2017.7.29
补充一份加了当前弧优化&&把cap和flow两个变量合成一个的代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #include<algorithm>
7 using namespace std;
8 const int MAXN=10000001;
9 const int MAXM=30000001;
10 const int maxn=0x7fffff;
11 inline void read(int &n)
12 {
13 char c='+';int x=0;bool flag=0;
14 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
15 while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
16 flag==1?n=-x:n=x;
17 }
18 struct node
19 {
20 int u,v,f,nxt;
21 }edge[MAXM];
22 int head[MAXN];
23 int num=0;
24 int n,m,s,t;
25 inline void add_edge(int x,int y,int z)
26 {
27 edge[num].u=x;
28 edge[num].v=y;
29 edge[num].f=z;
30 edge[num].nxt=head[x];
31 head[x]=num++;
32 }
33 int ans=0;
34 int deep[MAXN];
35 int cur[MAXN];
36 inline bool bfs()
37 {
38 memset(deep,0,sizeof(deep));
39 deep[s]=1;
40 queue<int>q;
41 q.push(s);
42 while(q.size()!=0)
43 {
44 int p=q.front();
45 q.pop();
46 for(int i=head[p];i!=-1;i=edge[i].nxt)
47 if(!deep[edge[i].v]&&edge[i].f)
48 {
49 deep[edge[i].v]=deep[edge[i].u]+1;
50 q.push(edge[i].v);
51 }
52
53 }
54 return deep[t];
55 }
56 int dfs(int now,int a)
57 {
58 if(now==t||a<=0)
59 return a;
60 int totflow=0,curflow;
61 for(int &i=cur[now];i!=-1;i=edge[i].nxt)
62 {
63 if(edge[i].f&&deep[edge[i].v]==deep[edge[i].u]+1)
64 {
65 curflow=dfs(edge[i].v,min(a,edge[i].f));
66 edge[i].f-=curflow;
67 edge[i^1].f+=curflow;
68 totflow+=curflow;
69 a-=curflow;
70 if(a<=0) break;
71 }
72 }
73 return totflow;
74 }
75 inline void Dinic()
76 {
77 while(bfs())
78 {
79 for(int i=0;i<=n;i++)
80 cur[i]=head[i];
81 ans+=dfs(s,maxn);
82 }
83
84 printf("%d",ans);
85 }
86 int main()
87 {
88 read(n);read(m);read(s);read(t);
89 memset(head,-1,sizeof(head));
90 for(int i=1;i<=m;i++)
91 {
92 int x,y,z;
93 read(x);read(y);read(z);
94 add_edge(x,y,z);
95 add_edge(y,x,0);
96 }
97 Dinic();
98 return 0;
99 }