【您有新的未分配天赋点】网络流：从懵逼到完全懵逼

今天呢@assassain julao讲了一个在OI中极其重要，极其有趣，把无数人坑退役的知识点：网络流。

网络流呢顾名思义，就是在一个图中边有流量的限制，并根据这些流量限制做一些跟这个有关的事（ti）情（mu）。什么，范围？按zzh神犇的话来说，就是考试中那些看上去像是dp却又推不出式子的问题的通用解法。

按照问题的倾向，我们将问题分为三类：最大流、最小割、最小费用流。

大家看好我要开始口胡了

首先我们研究最大流，介绍最大流大部分解法原理，增广路定理：只要存在增广路，流就可以继续增大。证明显而易见，这里省去其实是我不会证。运用这一定理的算法有多种，这里只介绍最常见的Dinic算法。Dinic的原理可以概括为“层次图”和“阻塞流”，即不断使用bfs构造出层次图，在层次图中每一层多路增广，卡掉小边，最后从源点到不了汇点的时候流的大小即为最大流。图中最多有n层，会扩展n次，每次扩展中有n个节点搜索，进退流m次，因此单次增广时间复杂度为$O(nm)$，总的时间复杂度上限为$O(n^2m)$，实际上远没有这么差，如果是二分图匹配这种情况，甚至可以证（chui）明（bi）出时间复杂度为$O(sqrt{n}m)$，浮动太大，因此接下来我们将不再讨论时间复杂度问题明明是你太蒻讨论不了啊喂，只认为时间复杂度有两种可能：$O(能过)$、$O(不能过)$。直接贴板子。

 1 int S,T;
 2 int f[maxn][maxn],num[maxn][maxn],cnt,dist[maxm];
 3 int flag[maxn][maxn];
 4 bool bfs()
 5 {
 6     memset(dist,-1,sizeof(dist));
 7     dist[S]=1;
 8     queue<int>q;q.push(S);
 9     while(!q.empty())
10     {
11         int t=q.front();q.pop();
12         for(int i=head[t];i!=-1;i=edge[i].next)
13         {
14             int v=edge[i].to;
15             if(edge[i].flow>0&&dist[v]<0)
16             {
17                 dist[v]=dist[t]+1;
18                 q.push(v);
19                 if(v==T)return 1;
20             }
21         }
22     }
23     return 0;
24 }
25 int dfs(int pos,int flow)
26 {
27     if(pos==T)return flow;
28     for(int i=head[pos];i!=-1;i=edge[i].next)
29     {
30         int v=edge[i].to;
31         if(dist[pos]+1==dist[v]&&edge[i].flow>0)
32         {
33             int t=dfs(v,min(flow,edge[i].flow));
34             if(t>0)
35             {
36                 edge[i].flow-=t;
37                 edge[i^1].flow+=t;
38                 return t;
39             }
40         }
41     }
42     return 0;
43 }
44 int Dinic()
45 {
46     int ans=0,cnt;
47     while(bfs())
48            while(cnt=dfs(S,inf))ans+=cnt;
49     return ans;
50 }

板子

接下来我们继续口胡来看最小割，对于最小割有最小割定理：最小割=最大流。证明如下：

开始Ctrl+C @assassainPPT

证明：对于一个割来说，所有从s到t的流量必定经过删除的边，那么Max_flow一定 ≤ 割的值，同理可以推出Max_flow ≤ 任意割的值。
下面来看一个已经跑完最大流的残余网络，此时图中已没有从s到t的路径。将s和s能到达的所有点划分为S集，剩余点为T集。中间的所有边为一个割且均满载（剩余容量为0），那么当前流也就是最大流等于割的值，又因割的值大于等于最大流，所以此时的割即为最小割，且与最大流相等。

Ctrl+C完啦

最后我们来看玄学之王费用流。通过最大流定理我们可以知道找增广路就可以得到最大流，那么我们只要在找增广路时贪心找到单位流量费用最小增广路即可。这个证明比较简单，留给读者思考。你又不会了是不是啊。根据思（chang）考（shi），我们可以发现SPFA的时间复杂度比较小，可以保留在Dinic接近$O(不能过)$时过掉的希望。然而SPFA自己的时间复杂度也是$O(玄学)$的，因此，费用流的时间复杂度更加难以预测，大多数时间只能看情况考虑赌脸。

（证明自己是个欧洲人的机会来了）

板子嘛……还没打……留坑待填（逃

UPD：填坑啦……下面有板子……

今天大概就是这样，如果还有什么新的体会我会继续更新然而你不是哪篇最后都没更新完成……

UPD @ 2017/7/30 06:27：貌似昨天@assassain 的板子是比较慢的==

这个才是更快更不看脸的板子全T

 1 int S,T;
 2 int f[maxn][maxn],a[maxn][maxn],b[maxn][maxn],ax[maxn][maxn],ay[maxn][maxn],dist[20010];
 3 long long ans;
 4 bool bfs()
 5 {
 6     memset(dist,0,sizeof(dist));
 7     dist[S]=1;
 8     queue<int>q;q.push(S);
 9     while(!q.empty())
10     {
11         int t=q.front();q.pop();
12         for(int i=head[t];i!=-1;i=edge[i].next)
13         {
14             int v=edge[i].to;
15             if(edge[i].flow>0&&!dist[v])
16             {
17                 dist[v]=dist[t]+1;
18                 q.push(v);
19                 if(v==T)return 1;
20             }
21         }
22     }
23     return 0;
24 }
25 int g[20010];
26 int dfs(int pos,int flow)//我可能打了一个假的dfs……
27 {
28     if(pos==T||!flow)return flow;
29     int f=0;
30     for(int &i=g[pos];i!=-1;i=edge[i].next)//卡常神器……
31     {
32         int v=edge[i].to;
33         if(dist[pos]+1==dist[v]&&edge[i].flow>0)
34         {
35             int t=dfs(v,min(flow,edge[i].flow));
36             if(t>0)
37             {
38                 f+=t,flow-=t;
39                 edge[i].flow-=t;
40                 edge[i^1].flow+=t;
41                 if(!flow)break;
42             }
43         }
44     }
45     return f;
46 }
47 int Dinic()
48 {
49      while(bfs())
50     {
51         for(int i=S;i<=T;i++)g[i]=head[i];
52         tmp=dfs(S,inf);
53         cnt+=tmp;
54     }
55 }

改·板子

UPD2 @ 2017/7/30 20:14：

嗯从昨天晚上到现在做了一些题，现在就这些题继续口胡。

cogs14 搭配飞行员

链接：http://cogs.pro/cogs/problem/problem.php?pid=14

题意：求出二分图最大匹配。

裸的二分图最大匹配，没啥说的。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 using namespace std;
 7 const int maxn=105,maxm=10005,inf=0x7fffffff;
 8 const int S=0,T=101;
 9 struct node
10 {
11     int from,to,flow,next;
12 }edge[maxm<<1];
13 int head[maxn],tot;
14 void addedge(int u,int v,int w)
15 {
16     edge[tot]=(node){u,v,w,head[u]};head[u]=tot++;
17 }
18 int n,n1;
19 int dist[maxn];
20 bool bfs()
21 {
22     memset(dist,-1,sizeof(dist));
23     dist[S]=1;
24     queue<int>q;q.push(S);
25     while(!q.empty())
26     {
27         int t=q.front();q.pop();
28         for(int i=head[t];i!=-1;i=edge[i].next)
29         {
30             int v=edge[i].to;
31             if(edge[i].flow>0&&dist[v]<0)
32             {
33                 dist[v]=dist[t]+1;
34                 q.push(v);
35             }
36         }
37     }
38     if(dist[T]<0)return 0;
39     return 1;
40 }
41 int dfs(int pos,int flow)
42 {
43     if(pos==T)return flow;
44     for(int i=head[pos];i!=-1;i=edge[i].next)
45     {
46         int v=edge[i].to,t;
47         if(dist[v]==dist[pos]+1)
48             if(t=dfs(v,min(flow,edge[i].flow)))
49             {
50                 edge[i].flow-=t;
51                 edge[i^1].flow+=t;
52                 return t;
53             }
54     }
55     return 0;
56 }
57 int haha()
58 {
59     freopen("flyer.in","r",stdin);
60     freopen("flyer.out","w",stdout);
61     memset(head,-1,sizeof(head));
62     scanf("%d%d",&n,&n1);
63     for(int i=1;i<=n1;i++)addedge(S,i,1),addedge(i,S,0);
64     for(int i=n1+1;i<=n;i++)addedge(i,T,1),addedge(T,i,0);
65     int x,y;
66     while(scanf("%d%d",&x,&y)!=EOF)addedge(x,y,1),addedge(y,x,0);
67     int ans=0,flow;
68     while(bfs())
69         while(flow=dfs(S,inf))
70             ans+=flow;
71     printf("%d
",ans);
72     //while(1);
73 }
74 int sb=haha();
75 int main(){;}

cogs14

cogs2051 王者之剑（EX咖喱棒（手动滑稽））

cogs734 方格取数问题

链接：http://cogs.pro/cogs/problem/problem.php?pid=2051、http://cogs.pro/cogs/problem/problem.php?pid=734

题意：二者都是一样的，相邻格子的物品不能同时选择，求出物品最大数量。

首先对矩阵中每个点进行黑白染色，从源点向黑点容量为该点物品的边，由白点连出相同的边，相邻黑点白点之间连出容量无限大的边。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=35,maxm=3005,maxe=30005;
 7 int S,T;
 8 struct node
 9 {
10     int from,to,flow,next;
11 }edge[maxe<<1];
12 int head[maxm],Tot;
13 void addedge(int u,int v,int w)
14 {
15     edge[Tot]=(node){u,v,w,head[u]};head[u]=Tot++;
16     edge[Tot]=(node){v,u,0,head[v]};head[v]=Tot++;
17 }
18 int n,m,map[maxn][maxn],flag[maxn][maxn],cnt,num[maxn][maxn],dist[maxm];
19 long long tot;
20 const int inf=2147483647;
21 #include<queue>
22 bool bfs()
23 {
24     memset(dist,0,sizeof(dist));
25     dist[S]=1;
26     queue<int>q;q.push(S);
27     while(!q.empty())
28     {
29         int t=q.front();q.pop();
30         for(int i=head[t];i!=-1;i=edge[i].next)
31         {
32             int v=edge[i].to;
33             if(!dist[v]&&edge[i].flow>0)
34             {
35                 dist[v]=dist[t]+1;
36                 q.push(v);
37             }
38         }
39     }
40     return dist[T];
41 }
42 int dfs(int pos,int flow)
43 {
44     if(pos==T||!flow)return flow;
45     int f=0;
46     for(int i=head[pos];i!=-1;i=edge[i].next)
47     {
48         int v=edge[i].to;
49         if(dist[v]==dist[pos]+1&&edge[i].flow>0)
50         {
51             int t=dfs(v,min(flow,edge[i].flow));
52             if(t>0)
53             {
54                 flow-=t;f+=t;
55                 edge[i].flow-=t;
56                 edge[i^1].flow+=t;
57                 if(!flow)break;
58             }
59         }
60     }
61     return f;
62 }
63 int haha()
64 {
65     freopen("grid.in","r",stdin);
66     freopen("grid.out","w",stdout);
67     memset(head,-1,sizeof(head));
68     scanf("%d%d",&n,&m);
69     for(int i=1;i<=n;i++)
70     {
71         if(i%2==0)flag[i][0]=1;
72         for(int j=1;j<=m;j++)
73         {
74             scanf("%d",&map[i][j]);
75             tot+=map[i][j];
76             num[i][j]=++cnt;
77             flag[i][j]=(flag[i][j-1]^1);
78         }
79     }
80     S=0,T=n*m+1;
81     for(int i=1;i<=n;i++)
82         for(int j=1;j<=m;j++)
83             if(!flag[i][j])addedge(S,num[i][j],map[i][j]);
84             else addedge(num[i][j],T,map[i][j]);
85     for(int i=1;i<=n;i++)
86         for(int j=1;j<=m;j++)
87             if(!flag[i][j])
88             {
89                 if(i>1)addedge(num[i][j],num[i-1][j],inf);
90                 if(i<n)addedge(num[i][j],num[i+1][j],inf);
91                 if(j>1)addedge(num[i][j],num[i][j-1],inf);
92                 if(j<m)addedge(num[i][j],num[i][j+1],inf);
93             }
94     long long ans=0;
95     while(bfs())ans+=dfs(S,inf);
96     printf("%lld
",tot-ans);
97 }
98 int sb=haha();
99 int main(){;}

cogs734

cogs1873 happiness

链接：http://cogs.pro/cogs/problem/problem.php?pid=1873

题意：求出全图最大权闭合子图。

普通的最小割问题，建边时要注意，连到源点、汇点边权要加上合作值的一半，两个点之间边为双向。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 const int maxn=105,maxm=10005,inf=0x7fffffff;
  8 struct node
  9 {
 10     int from,to,flow,next;
 11 }edge[maxm*40];
 12 int head[maxm<<1],tot,n,m;
 13 void addedge(int u,int v,int w)
 14 {
 15     edge[tot]=(node){u,v,w,head[u]};head[u]=tot++;
 16     edge[tot]=(node){v,u,0,head[v]};head[v]=tot++;
 17 }
 18 int S,T;
 19 int f[maxn][maxn],a[maxn][maxn],b[maxn][maxn],ax[maxn][maxn],ay[maxn][maxn],dist[20010];
 20 long long ans;
 21 bool bfs()
 22 {
 23     memset(dist,0,sizeof(dist));
 24     dist[S]=1;
 25     queue<int>q;q.push(S);
 26     while(!q.empty())
 27     {
 28         int t=q.front();q.pop();
 29         for(int i=head[t];i!=-1;i=edge[i].next)
 30         {
 31             int v=edge[i].to;
 32             if(edge[i].flow>0&&!dist[v])
 33             {
 34                 dist[v]=dist[t]+1;
 35                 q.push(v);
 36                 if(v==T)return 1;
 37             }
 38         }
 39     }
 40     return 0;
 41 }
 42 int g[20010];
 43 int dfs(int pos,int flow)
 44 {
 45     if(pos==T||!flow)return flow;
 46     int f=0;
 47     for(int &i=g[pos];i!=-1;i=edge[i].next)
 48     {
 49         int v=edge[i].to;
 50         if(dist[pos]+1==dist[v]&&edge[i].flow>0)
 51         {
 52             int t=dfs(v,min(flow,edge[i].flow));
 53             if(t>0)
 54             {
 55                 f+=t,flow-=t;
 56                 edge[i].flow-=t;
 57                 edge[i^1].flow+=t;
 58                 if(!flow)break;
 59             }
 60         }
 61     }
 62     return f;
 63 }
 64 int haha()
 65 {
 66     freopen("nt2011_happiness.in","r",stdin);
 67     freopen("nt2011_happiness.out","w",stdout);
 68     memset(head,-1,sizeof(head));
 69     scanf("%d%d",&n,&m);
 70     S=0,T=n*m+1;
 71     for(int ct=0,i=1;i<=n;i++)
 72         for(int j=1;j<=m;j++)f[i][j]=++ct;
 73     int x;
 74     for(int i=1;i<=n;i++)
 75         for(int j=1;j<=m;j++)
 76         {
 77             scanf("%d",&x);
 78             ans+=x;a[i][j]=(x<<1);
 79         }
 80     for(int i=1;i<=n;i++)
 81         for(int j=1;j<=m;j++)
 82         {
 83             scanf("%d",&x);
 84             ans+=x;b[i][j]=(x<<1);
 85         }
 86     for(int i=1;i<n;i++)
 87         for(int j=1;j<=m;j++)
 88         {
 89             scanf("%d",&x);
 90             ans+=x;
 91             ax[i][j]+=x;
 92             a[i][j]+=x;a[i+1][j]+=x;
 93         }
 94     for(int i=1;i<n;i++)
 95         for(int j=1;j<=m;j++)
 96         {
 97             scanf("%d",&x);
 98             ans+=x;
 99             ax[i][j]+=x;
100             b[i][j]+=x;b[i+1][j]+=x;
101         }
102     for(int i=1;i<=n;i++)
103         for(int j=1;j<m;j++)
104         {
105             scanf("%d",&x);
106             ans+=x;
107             ay[i][j]+=x;
108             a[i][j]+=x;a[i][j+1]+=x;
109         }
110     for(int i=1;i<=n;i++)
111         for(int j=1;j<m;j++)
112         {
113             scanf("%d",&x);
114             ans+=x;
115             ay[i][j]+=x;
116             b[i][j]+=x;b[i][j+1]+=x;
117         }
118     for(int i=1;i<n;i++)
119         for(int j=1;j<=m;j++)addedge(f[i][j],f[i+1][j],ax[i][j]),addedge(f[i+1][j],f[i][j],ax[i][j]);
120     for(int i=1;i<=n;i++)
121         for(int j=1;j<m;j++)addedge(f[i][j],f[i][j+1],ay[i][j]),addedge(f[i][j+1],f[i][j],ay[i][j]);
122     for(int i=1;i<=n;i++)
123         for(int j=1;j<=m;j++)addedge(S,f[i][j],a[i][j]),addedge(f[i][j],T,b[i][j]);
124     long long cnt=0,tmp;
125     while(bfs())
126     {
127         for(int i=S;i<=T;i++)g[i]=head[i];
128         tmp=dfs(S,inf);
129         cnt+=tmp;
130     }
131     cnt/=2;
132     printf("%lld
",ans-cnt);
133 }
134 int sb=haha();
135 int main(){;}

cogs1873

cogs461 餐巾

链接：http://cogs.pro/cogs/problem/problem.php?pid=461

经典的餐巾计划问题。

费用流第一题……运用拆点的思想，将每一个点拆成入点和出点，源点向入点连容量为需求量，花费为0的边，出点向汇点连相同的边，同时从源点向出点连容量无限，花费为购买花费的边，然后在快洗、慢洗的几天开头那一天的入点和结束那一天终点之间连容量无限，花费为快（慢）洗代价的边。因为前一天的餐巾可以留到后一天用，所以还需要在连续两天入点之间连接容量无限，花费为0的边。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=510,maxm=8010,inf=0x7fffffff;
 7 struct node
 8 {
 9     int from,to,flow,cost,next;
10 }edge[maxm];
11 int head[maxn],tot;
12 void addedge(int u,int v,int w,int x)
13 {
14     edge[tot]=(node){u,v,w,x,head[u]};head[u]=tot++;
15     edge[tot]=(node){v,u,0,-x,head[v]};head[v]=tot++;
16 }
17 int need[maxn],S,T;
18 int n,b,f,fc,s,sc;
19 #include<queue>
20 int path[maxn],dis[maxn],vis[maxn];
21 int spfa(int S,int T)
22 {
23     for(int i=S+1;i<=T;i++)dis[i]=inf;
24     queue<int>q;q.push(S);vis[S]=1;
25     while(!q.empty())
26     {
27         int u=q.front();q.pop();vis[u]=0;
28         for(int i=head[u];i!=-1;i=edge[i].next)
29         {
30             int v=edge[i].to;
31             if(edge[i].flow>0&&dis[v]>dis[u]+edge[i].cost)
32             {
33                 dis[v]=dis[u]+edge[i].cost;
34                 if(!vis[v])
35                 {
36                     vis[v]=1;
37                     q.push(v);
38                 }
39                 path[v]=i;
40             }
41         }
42     }
43     return dis[T]==inf?0:dis[T];
44 }
45 int aug(int S,int T)
46 {
47     int f=inf,p=T;
48     while(p!=S)
49     {
50         f=min(f,edge[path[p]].flow);
51         p=edge[path[p]].from;
52     }
53     p=T;
54     while(p!=S)
55     {
56         edge[path[p]].flow-=f;
57         edge[path[p]^1].flow+=f;
58         p=edge[path[p]].from;
59     }
60     return f;
61 }
62 int MCMF(int S,int T)
63 {
64     int ret=0,d;
65     while(d=spfa(S,T))
66         ret+=aug(S,T)*d;
67     return ret;
68 }
69 int haha()
70 {
71     freopen("napkin.in","r",stdin);
72     freopen("napkin.out","w",stdout);
73     memset(head,-1,sizeof(head));
74     scanf("%d",&n);S=0,T=n*2+1;
75     for(int i=1;i<=n;i++)scanf("%d",&need[i]);
76     scanf("%d%d%d%d%d",&b,&f,&fc,&s,&sc);
77     for(int i=1;i<=n;i++)
78     {
79         addedge(S,i,need[i],0);
80         addedge(S,i+n,inf,b);
81         addedge(i+n,T,need[i],0);
82         if(i+f<=n)addedge(i,i+f+n,inf,fc);
83         if(i+s<=n)addedge(i,i+s+n,inf,sc);
84         if(i!=n)addedge(i,i+1,inf,0);
85     }
86     printf("%d
",MCMF(S,T));
87 }
88 int sb=haha();
89 int main(){;}

cogs461

唔大概就这样了吧……

只要是活着的东西，就算是神我也杀给你看。