poj 2516 Minimum Cost (最小費用最大流)

題目鏈接: 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 
#include 
#include 
#define MAX 110
#define INF 0x3f3f3f3f
#define Min(a,b) ((a=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]