学步园

题目链接:   poj 2516

题目大意:   给出N间商店和它们对K种商品的需求，再给出M个供应商和K种商品的库存

                  然后再给出第x种商品从j供应商运输到i商店的单位运输费用

                  求N间商店对商品的需求能否得到满足，并且输出最小费用

解题思路:   如果直接建图会超时，因为顶点数太多

                  所以根据每种商品，进行K次最小费用流：

                  1.建立超级源点，源点指向N间商店，容量为第i间商店对第i1种商品的需求，费用为0

                  2.建立超级汇点，M个供应商指向汇点，容量为第j个供应商的第i1种商品的库存，费用为0

                  3.建立N*M条边，每条边从第i间商店指向第j个供应商，容量为无穷大(20000)，费用为单位运输费用

                  PS: 最小费用最大流与一般增广路的区别在于，每次寻找的增广路都是代价最小的路径

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 110
#define INF 0x3f3f3f3f
#define Min(a,b) ((a<b)?a:b)
int S,E,Index,dist[MAX],pre[MAX],visit[MAX],listb[2000010];
int path[MAX],In1[53][53],In2[53][53],In3[53][53][53];
int Map[MAX][MAX],Value[MAX][MAX];

struct snode{
    int c,w,to,next;
}Edge[MAX*MAX*10];

void Add_edge(int a,int b,int c,int d)
{
    Value[a][b]=d;     //标记改变的费用
    if(c>=0)            //构建残留网络
        Map[a][b]=c;
    Edge[Index].to=b,Edge[Index].c=c;
    Edge[Index].w=d,Edge[Index].next=pre[a];
    pre[a]=Index++;
}

bool BFS()
{
    int i,e,s,v,vv;
    s=e=0;
    memset(path,-1,sizeof(path));
    memset(dist,INF,sizeof(dist));
    memset(visit,0,sizeof(visit));
    listb[s++]=S;visit[S]=1; dist[S]=0;
    while(s!=e)
    {
        v=listb[e++];
        visit[v]=0;
        for(i=pre[v];i!=-1;i=Edge[i].next)
        {
            vv=Edge[i].to;
            if(Map[v][vv]>0&&(dist[vv]==INF||dist[vv]>dist[v]+Edge[i].w))
            {     //最短路寻找代价最小的增广路
                path[vv]=v;
                dist[vv]=dist[v]+Edge[i].w;
                if(!visit[vv])      //防止重复入队列
                {
                    visit[vv]=1;
                    listb[s++]=vv;
                }
            }
        }
    }
    if(dist[E]==INF)  //不能到达汇点，增广结束
        return false;
    return true;
}

int Find()
{
    int sum=0,i,MIN=INF;
    for(i=E;i!=-1;i=path[i])     //找短板
    {
        if(path[i]!=-1)
            MIN=Min(MIN,Map[path[i]][i]);
    }
    for(i=E;i!=-1;i=path[i])     //更新增广路
    {
        if(path[i]!=-1)
        {
            Map[path[i]][i]-=MIN;
            Map[i][path[i]]+=MIN;
            sum=sum+Value[path[i]][i]*MIN;  //代价是每条边的权值，所以不需要乘与
        }
    }
    return sum;
}

int Solve()
{
    int sum=0;
    while(BFS())
        sum+=Find();
    return sum;
}

int main()
{
    int i,n,j,m,k,aa[52],bb[52],pd;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        Index=pd=0;
        if(n==0&&m==0&&k==0)
            break;
        memset(pre,-1,sizeof(pre));
        memset(Map,0,sizeof(Map));
        memset(Value,0,sizeof(Value));
        memset(aa,0,sizeof(aa));
        memset(bb,0,sizeof(bb));
        int a,b,c,d;
        S=0,E=n*k+m*k+1;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=k;j++)
            {
                scanf("%d",&In1[i][j]);
                aa[j]+=In1[i][j];
            }
        }
        for(i=1;i<=m;i++)
        {
            for(j=1;j<=k;j++)
           {
               scanf("%d",&In2[i][j]);
               bb[j]+=In2[i][j];
           }
        }
        for(int i1=1;i1<=k;i1++)
        {
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=m;j++)
                    scanf("%d",&In3[i1][i][j]);
            }
        }
        for(i=1;i<=k;i++)
        {
            if(bb[i]<aa[i])   //若不满足则直接输出-1
            {
                pd=1;
                break;
            }
        }
        if(pd==1)
        {
            printf("-1\n");
            continue;
        }
        int temp=0;
        S=0,E=n+m+1;
        for(i=1;i<=k;i++)
        {
            Index=0;
            memset(pre,-1,sizeof(pre));
            memset(Map,0,sizeof(Map));
            memset(Value,0,sizeof(Value));
            for(j=1;j<=n;j++)   //左边
            {
                a=S,b=j,c=In1[j][i],d=0;
                Add_edge(a,b,c,d);
                Add_edge(b,a,-c,-d);
            }
            for(j=1;j<=n;j++)   //中间
            {
                for(int j1=1;j1<=m;j1++)
                {
                    a=j,b=n+j1;
                    c=20000;
                    d=In3[i][j][j1];
                    Add_edge(a,b,c,d);
                    Add_edge(b,a,-c,-d);
                }
            }
            for(j=1;j<=m;j++)   //后面
            {
                a=n+j,b=E,c=In2[j][i],d=0;
                Add_edge(a,b,c,d);
                Add_edge(b,a,-c,-d);
            }
            temp+=Solve();
        }
        printf("%d\n",temp);
    }
    return 0;
}