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