网络流基础

感谢某个同学问我网络流问题的同学，让我在有生之年整理了一把网络流。

大部分资料来源于：洛谷暑期营的课件

一，一些关于网络流的概念

网络流图：一张有向连通图，有且只有一个点的入度为零，这个点称为源点，有且只有一个点的出度为零

这个点称为汇点，每个边有一个非负权值c称为这条边的容量。

容许流：在网络流图中，对于每条边 e = (i, j) 给定实数 fe ，如果满足 fe ≤ ce ；对于任意 x ̸= S,T ，

∑ e=(x,i) fe = ∑ e=(i,x) fe ；（流量平衡） ∑ e=(S,i) fe = ∑ e=(i,T) fe = W ，则这一组 f 称为

该网络的一个容许流，W 称为它的流量。

最大流：求一个容许流使得它的 W 最大，用通俗易懂的话说，最大流就是给源点赋一个数，你要让这个值能够通过

这张网络流图的路径流到汇点，你想让这个值尽量的大。

二，最大流算法

一类解决网络流求最大流问题的基本思想——Ford-Fulkerson 标号算法

该算法的核心思想为不断寻找增广路。

何为增广（源）路，就是找到一条从源点到汇点的路径，使得这条路径的流量不为零，就找到了一条增源路。

算法过程：

记录 ve = ce − fe ，为一条边的剩余可用容量。对于每一条边 e = (i, j) ，增加一条反向弧 e ′ = (j, i) ，ve’=0。

首先给 S 标号 (−, inf) 。不断检查，如果存在一个点 i 已被标号为 (di, δi) ，对于 e = (i, j) 有 ve > 0 且 j 未被标号，

则给 j 标号 (e, min(δi, ve)) 。（可以通过 DFS 或 BFS 实现）如果某个时刻 T 被标号，则找到了一条流量为 w = δT 的增广路，

将沿着 di 一路回到 S 的所有边 e 的 ve 减去 w ，同时将所有 v ′ e 增加 w 。如果 T 无法被标号，则说明当前容许流就是最大流。

建反向边的意义：让我们有“后悔”的机会

比如

显然，这张图的最大流为2，但我们找到的这条路为1，所以我们就让流量从3到2再流回去，这样就实现了“后悔”。

显然这个算法的效率比较差（是很差），它的效率和边的容量有直接关系，比如上图将1-2,2-4,1-3,3-4改为1e9后

这个算法最差执行2e9才会结束。

所以就出现了EdmondsKarp算法。

EdmondsKarp:每次沿着一条最短（边数）的增光路去增广，这样上图执行两次就可以结束，只需要在FF的基础上用BFS打标记即可。

至于为什么是BFS（最短路里如果边权为1，可以用BFS求最短路大家都会吧），就这样。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #define maxn 10010
 7 #define INF 2147483647
 8 
 9 using namespace std;
10 
11 struct node
12 {
13     int ed,nxt,len;
14 };
15 node edge[maxn*20];
16 int n,m,cnt=-1,first[maxn],S,T,ans;
17 int pre_u[maxn],pre_e[maxn],flow[maxn];
18 bool vis[maxn];
19 
20 inline void add_edge(int s,int e,int d)
21 {
22     ++cnt;
23     edge[cnt].ed=e;
24     edge[cnt].len=d;
25     edge[cnt].nxt=first[s];
26     first[s]=cnt;
27     return;
28 }
29 
30 inline bool bfs(int s,int t)
31 {
32     queue <int> q;
33     memset(vis,false,sizeof(vis));
34     memset(pre_u,-1,sizeof(pre_u));
35     memset(pre_e,-1,sizeof(pre_e));
36     memset(flow,0,sizeof(flow));
37     pre_u[s]=s; vis[s]=true; flow[s]=INF;
38     q.push(s);
39     while(!q.empty())
40     {
41         int p=q.front(); q.pop();
42         for(register int i=first[p];i!=-1;i=edge[i].nxt)
43         {
44             int e=edge[i].ed;
45             if(!vis[e]&&edge[i].len!=0)
46             {
47                 pre_u[e]=p;
48                 pre_e[e]=i;
49                 vis[e]=true;
50                 flow[e]=min(flow[p],edge[i].len);
51                 if(e==t) return true;
52                 q.push(e);
53             }
54         }
55     }
56     return false;
57 }
58 
59 inline void EK()
60 {
61     while(bfs(S,T))
62     {
63         for(register int i=T;i!=S;i=pre_u[i])
64         {
65             edge[pre_e[i]].len-=flow[T];
66             edge[pre_e[i]^1].len+=flow[T];
67         }
68         ans+=flow[T];
69     }
70     return;
71 }
72 
73 int main()
74 {
75     memset(first,-1,sizeof(first));
76     scanf("%d%d%d%d",&n,&m,&S,&T);
77     for(register int i=1;i<=m;++i)
78     {
79         int s,e,d;
80         scanf("%d%d%d",&s,&e,&d);
81         add_edge(s,e,d);
82         add_edge(e,s,0);
83     }
84     EK();
85     printf("%d
",ans);
86     return 0;
87 }

3，举世闻名的Dinic

让我们继续考虑优化EK，我们发现EK每次只会找到一条增广路，造成了时间的浪费，那么我们为什么不能一次

找多条增广路呢？？当然可以。

思路：bfs分层，dfs寻找路。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #define INF 2147483647
 7 #define maxn 10010
 8 
 9 using namespace std;
10 
11 struct node
12 {
13     int ed,len,nxt;
14 };
15 node edge[maxn*20];
16 int n,m,first[maxn],cnt=-1,dis[maxn];
17 int S,T,ans;
18 bool vis[maxn];
19 
20 inline void add_edge(int s,int e,int d)
21 {
22     ++cnt;
23     edge[cnt].ed=e;
24     edge[cnt].len=d;
25     edge[cnt].nxt=first[s];
26     first[s]=cnt;
27     return;
28 }
29 
30 inline bool bfs(int s,int t)
31 {
32     memset(dis,-1,sizeof(dis));
33     memset(vis,false,sizeof(vis));
34     queue <int> q;
35     dis[s]=0;
36     q.push(s);
37     while(!q.empty())
38     {
39         int p=q.front(); q.pop();
40         for(register int i=first[p];i!=-1;i=edge[i].nxt)
41         {
42             int e=edge[i].ed;
43             if((dis[e]==-1)&&edge[i].len!=0)
44             {
45                 dis[e]=dis[p]+1;
46                 q.push(e);
47             }
48         }
49     }
50     if(dis[t]==-1) return false;
51     else return true;
52 }
53 
54 inline int dfs(int s,int max_flow)
55 {
56     if(s==T) return max_flow;
57     int now_flow=0;
58     for(register int i=first[s];i!=-1;i=edge[i].nxt)
59     {
60         int e=edge[i].ed;
61         if(dis[e]==dis[s]+1&&edge[i].len!=0)
62         {
63             int flow=dfs(e,min(edge[i].len,max_flow));
64             if(!flow) continue;
65             edge[i].len-=flow;
66             edge[i^1].len+=flow;
67             max_flow-=flow;
68             now_flow+=flow;
69             if(!max_flow) break;
70         }
71     }
72     return now_flow;
73 }
74 
75 inline void dinic()
76 {
77     while(bfs(S,T)) ans+=dfs(S,INF);
78     return;
79 }
80 
81 int main()
82 {
83     scanf("%d%d%d%d",&n,&m,&S,&T);
84     memset(first,-1,sizeof(first));
85     for(register int i=1;i<=m;++i)
86     {
87         int s,e,d;
88         scanf("%d%d%d",&s,&e,&d);
89         add_edge(s,e,d);
90         add_edge(e,s,0);
91     }
92     dinic();
93     printf("%d
",ans);
94     return 0;
95 }

三，最小割定理

最小割：去除一些边，使得这些边的边权和尽量小的情况下，使得从源点到汇点不连通。

定理：最小割等于最大流