本次網絡流算法看了兩天了，先學習了EK算法，發現速度不夠快，於是查找資料，得網絡流諸多算法中主流算法（SAP算法）學習之。
相關鏈接：
1、網絡流的算法分類：http://www.notonlysuccess.com/index.php/algorithm-of-network/
2、牛人博客，幾種算法的分析：http://blog.csdn.net/abcjennifer/article/details/5556455
3、較詳細的SAP算法分析：http://hi.baidu.com/hewei156/blog/item/f17038326b2f91c0a2cc2b78.html
研究的一天多的代碼模版（該模版正確性及可用性有待證明，以後若出現什麼問題將進行修改）：
[cpp]
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<math.h>
#define maxn 205
#define INF 100000000
using namespace std;
int n,m,s,t;// n點數，m邊數，s起點，t終點
int map[maxn][maxn],fa[maxn],gap[maxn],level[maxn];//map有向圖，fa父節點，
//gap[i]=j表示以匯點距離為i的點有j個，level[i]=j表示點i與匯點距離為j
void sap_bfs()//反向 BFS 初始化所有頂點的距離標號、初始化level和gap數組
{
memset(level,1,sizeof(level));//這個很神奇，每個int的4字節都變成0000 0001
//即數組被初始化為二進制的00000001 00000001 00000001 00000001 ，十進制為16843009
memset(gap,0,sizeof(gap));
queue<int> q;
q.push(t);
level[t]=0;//匯點距離為0
gap[level[t]]++;
while(!q.empty())
{
int temp=q.front(); q.pop();
for(int i=1;i<=n;i++)
if(level[i]>n && map[i][temp]>0)
{
q.push(i);
level[i]=level[temp]+1;
gap[level[i]]++;
}
}
}
int fine_path(int u)//查找殘量網絡中是否有與u相連 且距離為1的點
{
for(int i=1;i<=n;i++) if(map[u][i]>0 && level[u]==level[i]+1)
return i;
return -1;
}
int Advance()//找到匯點時進行增廣
{
int i,minflow=INF;
for(i=t;i!=s;i=fa[i]) if(minflow>map[fa[i]][i])//查找這條增廣路中最小的流量
{
minflow=map[fa[i]][i];
}
for(i=t;i!=s;i=fa[i])
{
map[fa[i]][i]-=minflow;
map[i][fa[i]]+=minflow;//反向邊也要操作
}
return minflow;
}
int retreat(int u)//對點u重新設置最小的距離
{
int fine=INF;
for(int i=1;i<=n;i++) if(map[u][i]>0 && fine>level[i]+1)
fine=level[i]+1;
if(fine==INF) fine=n;//找不到的話設置為最大，即點u不會再被經過
return fine;
}
int cxbsap()
{
sap_bfs();
int i,j,v,u=s,flow=0;//初始化
while(level[s]<=n)//源點與匯點距離小於n時執行，要是不存在源點到匯點的通路直接跳出
{
v=fine_path(u);// 找u的下一個點
if(v>0)
{
fa[v]=u;//找到後標記父節點
u=v;//把v賦值給u，如果不是匯點，直接跳回75行了
if(u==t)
{
flow+=Advance();
u=s;//找的一條路徑後重新查找
}
}
else
{
if(--gap[level[u]]==0) return flow;//如果其中一個距離個數為0，即出現斷層，沒有通路看，直接跳出
v=retreat(u);
gap[v]++;
level[u]=v;
if(u!=s) u=fa[u];
}
}
return flow;
}
int main()
{
// freopen("in.txt","r",stdin);
int i,j,a,b,x;
while(~scanf("%d%d",&m,&n))
{
memset(map,0,sizeof(map));
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&x);
map[a][b]+=x;
}
s=1; t=n;
int ans=cxbsap();
printf("%d\n",ans);
}
return 0;
}
我發現其實自己有點強迫症，我喜歡帶參數的函數，所以：
[cpp]
/*
網絡流改進sap模版：HDU1532
計算一個點編號1~n的網絡的最大流；
時間復雜度o(v*e^2) v點數，e邊數
陳小賓，2012、8、13凌晨
*/
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<math.h>
#define maxn 205
#define INF 100000000
using namespace std;
int n,m;// n點數，m邊數，s起點，t終點
int map[maxn][maxn],fa[maxn],gap[maxn],level[maxn];//map有向圖，fa父節點，
//gap[i]=j表示以匯點距離為i的點有j個，level[i]=j表示點i與匯點距離為j
void sap_bfs(int t)//反向 BFS 初始化所有頂點的距離標號、初始化level和gap數組
{
memset(level,1,sizeof(level));//這個很神奇，每個int的4字節都變成0000 0001
//即數組被初始化為二進制的00000001 00000001 00000001 00000001 ，十進制為16843009
memset(gap,0,sizeof(gap));
queue<int> q;
q.push(t);
level[t]=0;//匯點距離為0
gap[level[t]]++;
while(!q.empty())
{
int temp=q.front(); q.pop();
for(int i=1;i<=n;i++)
if(level[i]>n && map[i][temp]>0)
{
q.push(i);
level[i]=level[temp]+1;
gap[level[i]]++;
}
}
}
int fine_path(int u)//查找殘量網絡中是否有與u相連 且距離為1的點
{
for(int i=1;i<=n;i++) if(map[u][i]>0 && level[u]==level[i]+1)
return i;
return -1;
}
int Advance(int s,int t)//找到匯點時進行增廣
{
int i,minflow=INF;
for(i=t;i!=s;i=fa[i]) if(minflow>map[fa[i]][i])//查找這條增廣路中最小的流量
{
minflow=map[fa[i]][i];
}
for(i=t;i!=s;i=fa[i])
{
map[fa[i]][i]-=minflow;
map[i][fa[i]]+=minflow;//反向邊也要操作
}
return minflow;
}
int retreat(int u)//對點u重新設置最小的距離
{
int fine=INF;
for(int i=1;i<=n;i++) if(map[u][i]>0 && fine>level[i]+1)
fine=level[i]+1;
if(fine==INF) fine=n;//找不到的話設置為最大，即點u不會再被經過
return fine;
}
int cxbsap(int s,int t)
{
sap_bfs(t);
int i,j,v,u=s,flow=0;//初始化
while(level[s]<=n)//源點與匯點距離小於n時執行，要是不存在源點到匯點的通路直接跳出
{
v=fine_path(u);// 找u的下一個點
if(v>0)
{
fa[v]=u;//找到後標記父節點
u=v;//把v賦值給u，如果不是匯點，直接跳回75行了
if(u==t)
{
flow+=Advance(s,t);
u=s;//找的一條路徑後重新查找
}
}
else
{
if(--gap[level[u]]==0) return flow;//如果其中一個距離個數為0，即出現斷層，沒有通路看，直接跳出
v=retreat(u);
gap[v]++;
level[u]=v;
if(u!=s) u=fa[u];
}
}
return flow;
}
int main()
{
// freopen("in.txt","r",stdin);
int i,j,a,b,x;
while(~scanf("%d%d",&m,&n))
{
memset(map,0,sizeof(map));
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&x);
map[a][b]+=x;
}
int ans=cxbsap(1,n);
printf("%d\n",ans);
}
return 0;
}
作者：cxb569262726
