今天呢@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\n",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\n",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\n",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\n",MCMF(S,T)); 87 } 88 int sb=haha(); 89 int main(){;} cogs461

?

唔大概就這樣了吧……

轉載于:https://www.cnblogs.com/Loser-of-Life/p/7257361.html

總結

以上是生活随笔為你收集整理的【您有新的未分配天赋点】网络流：从懵逼到完全懵逼的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。