PKU2516 Minimum Cost - 最小费用最大流

本文主要是介绍PKU2516 Minimum Cost - 最小费用最大流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

模板题，整理代码……

 /*
PKU2516 Minimum Cost
*/
#include <stdio.h> 
#include <memory.h> 
#define clr(a) memset(a,0,sizeof(a)) 
#define N 200 
#define INF (1<<25) 
int DualityEdmondsKarp(int g[][N],int w[][N],int n,int s,int t,int f[][N],int *minCost)
{
    int i,j,k,c,quit,flow=0,minw=0;
    int best[N],prev[N];
    for(i=0;i<n;i++)for(j=0;j<n;j++) {
        f[i][j]=0;
        if(g[i][j]) {
            g[j][i]=0; w[j][i]=-w[i][j];
        }
    }
    while(1) {
        for(i=0;i<n;i++)best[i]=INF;
        best[s]=0;
        do{
            quit=1;
            for(i=0;i<n;i++)if(best[i]<INF){
                for(j=0;j<n;j++)
                if(f[i][j]<g[i][j]&
                best[i]+w[i][j]<best[j]) {
                    best[j]=best[i]+w[i][j];
                    prev[j]=i;
                    quit=0;
                }
            }
        } while(!quit);
        if(best[t]>=INF)break ;
        for(c=INF,j=t;j!=s;j=i) {
            i=prev[j];
            if(c>g[i][j]-f[i][j])c=g[i][j]-f[i][j];
        }
        for(j=t;j!=s;j=i) {
            i=prev[j];
            f[i][j]+=c;
            f[j][i]=-f[i][j];
        }
        flow+=c;
        minw+=c*best[t];
    }
    *minCost = minw;
    return flow;
}
int a[N][N][N];
int w[N][N][N];
int f[N][N];
int main()
{
    int i,j,k;
    int n,m,h;
    int s,t,sum,all;
    while(scanf("%d%d%d",&n,&m,&h)!=EOF && n+m+h){
        //init 
        clr(a); clr(w);
        s=n+m; t=s+1;
        sum=0; all=0;
        for(k=0;k<h;k++)
        for(i=0;i<n;i++)for(j=0;j<m;j++){
            a[k][j][i+m]=INF;
        }
        
        //input 
        for(i=0;i<n;i++)for(k=0;k<h;k++){
            scanf("%d",&a[k][i+m][t]);
            sum+=a[k][i+m][t];
        }
        for(j=0;j<m;j++)for(k=0;k<h;k++){
            scanf("%d",&a[k][s][j]);
            all+=a[k][s][j];
        }
        for(k=0;k<h;k++)
        for(i=0;i<n;i++)for(j=0;j<m;j++)
            scanf("%d",&w[k][j][i+m]);
        //prejudge 
        if(sum>all){
            puts("-1"); continue;
        }
        //output 
        int cost=0,c;
        int total=0;
        for(k=0;k<h;k++){
            total+=DualityEdmondsKarp(a[k],w[k],n+m+2,s,t,f,&c);
            cost+=c;
        }
        if(total<sum) puts("-1");
        else printf("%d/n",cost);
    }
    return 0;
}
 