/************************************************************************
網絡流的定義好多呀 這里就僅僅標注定義名字吧 詳細解釋就交給以后的自己啦
==容量網絡和網絡最大流
1.容量 （容量網絡，弧的容量，弧的流量)
2.網絡流（可行流）—— 可行流的瞞住條件（弧流量限制條件&&平衡條件）
3.偽流
4.最大流
==鏈和增廣路
1.飽和弧（非飽和弧）
2.零流（非零流）
3.鏈
4.前向弧（后向弧）
5.增廣路
==殘留容量和殘留網絡
1.殘留容量（殘留網絡）
==割&&最小割
1.割
2.S-T割
3.割的容量（割的凈流量,最小割） K

?

￥￥最大流最小割定理

整體把關：
網絡最大流的求解分兩大類算法：1.增廣路算法（包括一般增光路算法Ford-Filkerson算法 最短增光路算法 連續最短增廣路算法） 2.預流推進算法(

///一般增廣路算法 純模板
#include <iostream> #include <string.h> #include <cmath> #include <stdio.h> using namespace std; #define INF 100000+10 #define Max 1000 struct Node { int c; ///容量 int f; ///流量 } mapp[Max][Max]; int pre[Max]; ///指明從哪個定點得到的 方便用到追蹤的方法得到可改進量
int alphp[Max]; ///用來存放每點之間的可改進量 int flag[Max]; ///標記該點是否已經檢查過了 int que[Max]; ///廣搜 模擬隊列 int qe,qs; ///隊尾 隊頭 int v; ///隊列頂點 int n,m; void Ford() { while(1) { ///0是起始點 memset(pre,-1,sizeof(pre)); memset(flag,-1,sizeof(flag)); memset(alphp,-1,sizeof(alphp)); flag[0]=0; pre[0]=0; alphp[0]=INF; ///之上是初始化三個數組 均標記為未使用 0點使用 0點前驅為0 0點的改進量==INF（意為0點可以流出無限多） qs=qe=0; ///隊列掃描 que[qe]=0; ///the begin of que[] qe++; while(qs<qe&&flag[n-1]==-1) { v=que[qs]; ///take the top of que[] qs++; for(int i=0; i<n; i++) { if(flag[i]==-1) { ///每次在改的過程 不斷更新點 邊； ///正方向未滿 so改進 if(mapp[v][i].c<INF&&mapp[v][i].f<mapp[v][i].c) { flag[i]=0; pre[i]=v; alphp[i]=min(alphp[v],mapp[v][i].c-mapp[v][i].f); que[qe]=i; qe++; } ///反向有流量（反向流） else if(mapp[i][v].c<INF&&mapp[i][v].f>0) { flag[i]=0; pre[i]=-v; alphp[i]=min(alphp[v],mapp[i][v].f); que[qe]=i; qe++; } } } flag[v]=1; } ///當隊列為空的時候 匯點還沒有被標記 或者匯點的調整量==0 則這次失敗了 跳出while循環 if(flag[n-1]==-1||alphp[n-1]==0) break; ///否者就應該到追蹤 更新調整了 int k1=n-1; ///最后一個點 int k2=abs(pre[k1]); ///與最后一個點連接的點（前一個點） int a=alphp[n-1]; ///可調整量 while(1) ///該路線一定是可調整路線 { if(mapp[k2][k1].f<INF) ///進行調整 在原有基礎上加上調整量（更新） 正向 { mapp[k2][k1].f+=a; } else ///反向 mapp[k1][k2].f-=a; if(k2==0) ///調整到原點了 break; k1=k2; //繼續向前追蹤 k2=abs(pre[k2]); } } int maxFlow=0; ///==最大流 for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(i==0&&mapp[i][j].f<INF) maxFlow+=mapp[i][j].f; if(mapp[i][j].f<INF) printf("%d->%d:%d\n",i,j,mapp[i][j].f); } } printf("maxFlow==%d\n",maxFlow); } int main() { // freopen("in.txt","r",stdin); int u,v,c,f; cin>>n>>m; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { mapp[i][j].c=mapp[i][j].f=INF; ///初始化 } } for(int i=0;i<m;i++) ///建圖 { cin>>u>>v>>c>>f; mapp[u][v].c=c; mapp[u][v].f=f; } Ford(); }///輸入輸出input:6 100 1 8 2
0 2 4 3
1 3 2 2
1 4 2 2
2 1 4 2
2 3 1 1
2 4 4 0
3 4 6 0
3 5 9 3
4 5 7 2
output：
0->1:4
0->2:4
1->3:2
1->4:2
2->1:0
2->3:1
2->4:3
3->4:0
3->5:3
4->5:5
maxFlow==8

///最短增光路算法最短增光路算法 最短增廣路算法
構造殘留網絡—>構造層次網絡——>BFS(刪去不可繼續增廣的邊，點）——>不存在增廣路為止；
///連續增光路
構造殘留網絡——>構造層次網絡——>DFS(每次DFS之后回退到起點能夠到達的最遠的點）——>回退到起點結束；
兩者之前的部分是一樣的 對應模板后續補上~~~

接下來打幾道網絡流的題吧~~（都是copy 但是我會詳細寫過程的！！！）
poj1149 poj1273 poj2112 poj1459 poj1087 poj2301 poj3436 poj1637

poj1149 一般增廣路算法 仔細理解題意
重點在構造網絡流
構造方法：
1. 我們將每一個豬圈看成除源點和匯點之外的點（所以我們需要添加源點和匯點）
2.源點和每個豬圈的第一個顧客相連接，邊的權值是豬圈開始時豬的數目（如果源點和某個邊重合了，則權值之和作為作為該邊新的權值） eg：第一個豬圈的第一個顧客是1 第二個豬圈也是 所以源點和1號顧客連邊的權值==4
3.顧客j緊跟著顧客i 則邊<i,j>=INF ,因為賣家可以在開j之前（就是在i顧客期間 隨意更換每個豬圈里豬的數目，所以j可以買到任意多的豬）
4.每個顧客和會點之間的連邊是顧客希望買到豬的數目（所以匯點的流入量==顧客想買豬的總數）


第一次插圖片 有些丑~~~~啦啦啦 構造的原始圖就是這樣的！！！！
接下來就是真正的代碼啦~~
#include <string.h>
#include <stdio.h>
#include <iostream>

using namespace std;
#define Maxm 1000
#define Maxn 10
#define INF 300000000

int s,t; ///源點 匯點
int cust[Maxn+2][Maxn+2];? ///節點之間的容量（包括源點和匯點）customer
int flow[Maxn+2][Maxn+2];? ///節點之間的流量

void init()
{
??? int n,m; ///豬圈數?? 顧客數
??? int num;? ///每個顧客擁有的鑰匙數
??? int house[Maxm];? ///每個豬圈中豬的數目
??? int last[Maxm]; ///每個豬圈的前一個顧客的序號?? 到追蹤的翻版
??? int k;? ///第k個豬圈的鑰匙
??? memset(last,0,sizeof(last));
??? memset(house,0,sizeof(house));
??? cin>>n>>m;
??? s==0;
??? t=n+1;? ///定義源點和匯點
??? for(int i=1; i<=m; i++)
??????? cin>>house[i];? ///注意角標從1開始?? 0給源點了
??? for(int i=1; i<=n; i++)
??? {
??????? cin>>num;
??????? for(int j=0; j<num; j++)
??????? {
??????????? cin>>k;? ///鑰匙的序號
??????????? if(last[k]==0)? ///開通豬圈的第一把鑰匙
??????????????? cust[s][i]+=house[k];? ///如果有重合邊? 權值相加
??????????? else
??????????????? cust[last[k]][i]=INF; ///如果前面有鑰匙開該豬圈? 則該連接邊的權值無窮大
??????????? last[k]=i;? ///更新其前驅~~
??????? }
??????? cin>>cust[i][t];? ///該顧客想買的豬的數量
??? }

??? ///整個圖已經構造完成
}

void Ford()
{
??? int pre[Maxn+2];? ///連接邊的前一個定點? 方便倒追蹤? 源點標號==-1?? 其他未標記的點標號初始==-2
??? int minflow[Maxn+2];? ///每個定點的可改進量
??? ///廣搜（必然隊列模擬呀）
??? int que[Maxn+2];
??? int qs,qe; ///隊頭? 隊尾
??? int v;? ///隊列定點==當前檢查的點
??? int p;?? ///可改進量? （cij-fij）
??? ///構造零流?? 假設之前豬圈沒有豬
??? memset(flow,0,sizeof(flow));

??? minflow[0]=INF;
??? ///進入廣搜
??? while(1)
??? {
??????? for(int i=0; i<Maxn+2; i++)
??????????? pre[i]==-2;
??????? pre[0]=-1;? ///源點
??????? qs=0;
??????? que[qs]=0;? ///定點qs入隊
??????? qe=1;
??????? while(qs<qe&&pre[t]==-2)? ///t是匯點
??????? {
??????????? ///當qs>=qe時? 說明隊列為空 標號不可以進行下去了
??????????? v=que[qs];
??????????? qs++;
??????????? for(int i=0; i<t+1; i++) ///從源點到匯點都包含在內的
??????????? {
??????????????? if(pre[i]==-2&&(p=cust[v][i]-flow[v][i]))
??????????????? {
??????????????????? pre[i]=v;
??????????????????? que[qe]=i;
??????????????????? qe++;
??????????????????? minflow[i]=(minflow[v]<p)?minflow[v]:p;
??????????????? }
??????????? }
??????? }
??????? if(pre[t]==-2)
??????????? break;? ///匯點沒有標號? 證明源點到匯點沒有通路了。。。
??????? int i,j;
??????? for(i=pre[t],j=t; i!=-1; j=i,i=pre[i])
??????? {
??????????? flow[i][j]+=minflow[t];
??????????? flow[j][i]-=flow[i][j];
??????? }
??????? for(i=0,p=0; i<t; i++)
??????????? p+=flow[i][t];
??????? cout<<p<<endl;
??? }
}

int main()
{
??? init();
??? Ford();
??? return 0;
}

轉載于:https://www.cnblogs.com/zhangying/p/4165321.html

總結

以上是生活随笔為你收集整理的网络流模板的全部內容，希望文章能夠幫你解決所遇到的問題。

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