TXT

# int max_flow(in

By Jeanne Arnold,2014-11-01 18:05
9 views 0
int max_flow(int n,int mat[][MAXN],vector list[],int source,int sink,int flow[][MAXN]){ int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j,r; if (source==sink) return inf; for (i=0;i

int max_flow(int n,int mat[][MAXN],vector list[],int source,int sink,int

flow[][MAXN]){

int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j,r;

if (source==sink) return inf;

for (i=0;i

for (j=0;j

for (;;){

for (i=0;i

pre[t=source]=source+1,d[t]=inf;

for (p=q=0;p<=q&&!pre[sink];t=que[p++])

for (r=0;r

i=list[t][r];

if (!pre[i]&&j=mat[t][i]-flow[t][i])

pre[que[q++]=i]=t+1,d[i]=d[t]

else if (!pre[i]&&j=flow[i][t])

pre[que[q++]=i]=-t-1,d[i]=d[t]

}

if (!pre[sink]) break;

for (i=sink;i!=source;)

if (pre[i]>0)

flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;

else

flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;

}

for (j=i=0;i

return j;

}

//求网络最大流,邻接阵形式

//返回最大流量

//传入网络节点数n,容量mat,源点source,汇点sink

//注意mat矩阵被修改

#define MAXN 100

#define inf 1000000000

int max_flow(int n,int mat[][MAXN],int source,int sink){

int v[MAXN],c[MAXN],p[MAXN],ret=0,i,j;

for (;;){

for (i=0;i

v[i]=c[i]=0;

for (c[source]=inf;;){

for (j=-1,i=0;i

if (!v[i]&&c[i]&&(j==-1||c[i]>c[j]))

j=i;

if (j<0) return ret;

if (j==sink) break;

for (v[j]=1,i=0;i

if (mat[j][i]>c[i]&&c[j]>c[i])

c[i]=mat[j][i]

}

for (ret+=j=c[i=sink];i!=source;i=p[i])

Report this document

For any questions or suggestions please email
cust-service@docsford.com