using?namespace?std;

const?int?MAX=100;

const?int?inf=1<<30;

queueQ;

int?ShortestAugmentingPath(int?n,int?source,int?sink,int?map[][MAX],int?flow[][MAX],int?pre_t[])

{

/*??n為頂點數?,source為源點,sink為匯點,map[][]記錄對應邊的最大容量，flow[][]記錄對應邊具有的正流量;

最后一次迭代的pre_t[]記錄了最小割,pre_t[i]?!=0?表示屬于源點集合??*/

if(source==sink)??//特殊情況處理

return?inf;

int?i,x;

int?visited[MAX];????//visited[i]=1表示頂點i被標記

int?rest[MAX][MAX];??//rest[i][j]表示頂點i到j的未使用流量

int?L[MAX];???//L[i]記錄一次迭代過程中節點i的最大增量

int?pre[MAX];?//pre[i]=0表示頂點i未標記,pre[i]?>0?表示前向邊,pre[i]?

//數組初始化

memset(rest,0,sizeof(rest));

memset(visited,0,sizeof(visited));

memset(flow,0,(n+1)*sizeof(flow[0]));

memset(L,0x7f,n*sizeof(L[0]));

memset(pre,0,sizeof(pre));

pre[source]=source+1;??//任意賦值為一個整數

while(!Q.empty())

Q.pop();

Q.push(source);??//最初，源點入隊

while(!Q.empty())

{

visited[source]=1;??//源點被標記

i=Q.front();

Q.pop();

for(x=1;x<=n;x++)?//前向邊

{

if(i!=x&&!visited[x]&&map[i][x]!=inf)

{

rest[i][x]=map[i][x]-flow[i][x];

if(?rest[i][x]?>?0?)

{

L[x]=L[i]?

Q.push(x);

visited[x]=1;

pre[x]=i;

}

}

}

for(x=1;x<=n;x++)??//后向邊

{

if(i!=x&&!visited[x]&&map[x][i]!=inf)

{

if(flow[x][i]?>?0)

{

L[x]=L[i]?

Q.push(x);

visited[x]=1;

pre[x]=-i;

}

}

}

for(int?y=1;y<=n;y++)??//記錄最后一次迭代結果的標記,即為最小割

pre_t[y]=pre[y];

if(visited[sink]==1)?//匯點被標記了

{

x=sink;

while(x!=source)?//從匯點開始用第二個標記反向移動

{

if(pre[x]>0)

flow[i][x]?+=?L[sink];

else

flow[i][x]?-=?L[sink];

x=i;

if(pre[i]>0?)

i=pre[i];

else

i=-pre[i];

}

memset(visited,0,sizeof(visited));?//擦除標記

memset(L,0x7f,n*sizeof(L[0]));

while(!Q.empty())

Q.pop();

Q.push(source);?//用源點對q重新初始化

memset(pre,0,sizeof(pre));

pre[source]=1;

}

}

int?maxflow=0;

for(i=1;?i?<=?n;i++)

maxflow+=flow[i][sink];

return?maxflow;

}

int?main()

{

int?map[MAX][MAX],flow[MAX][MAX],pre[MAX];

int?n,i,x,w;

cout<

while(cin>>n?&&?n)

{

for(i=1;i<=n;i++)

{

for(x=1;x<=n;x++)

map[i][x]=inf;

}

int?m;?//輸入邊數

cout<

cin>>m;

cout<

while(m--)

{

cin>>i>>x>>w;

map[i][x]=w;

}

cout<

cout<

for(i=1;i<=n;i++)

{

if(pre[i]!=0?)

cout<

}

cout<

for(i=1;i<=n;i++)

{

if(pre[i]==0)

cout<

}

cout<

}

return?0;

}

總結

以上是生活随笔為你收集整理的最大流最小割经典例题_C/C++知识点之最大流最小割C++实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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