最大流最小割經典例題_C/C++知識點之最大流最小割C++實作

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[])

{

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;

}