poj 2516 Minimum Cost 夜

此题和2195题是一个题型

不同之处在于此题需要对每种物品均求一次最小花费然后合计

而且每种物品还要看是否满足了需求量有一种物品不满足的话就输出-1

我的方法很笨依次对每种物品进行求解

而且由于流很小我直接用了每次流都是减一下个题应该就不行了（我猜）

详情见代码注释

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>

using namespace std;
const int N=105;
const int M=100000005;
int have[N][N];//应有者对第几种物品的供应量
int need[N][N];//需求者对第几中物品的需求量
int goodpay[N][N][N];//第几种物品传送的单位花费
int flow[N][N];//流量 需要对不同的物品每次更新
int pay[N][N];//花费 需要对不同的物品每次更新
int Spfa(int n)
{
    bool in[N];
    int dist[N];
    int f[N];
    for(int i=1;i<=n;++i)
    {
        dist[i]=M;
    }
    memset(in,false,sizeof(in));
    dist[0]=0;
    queue<int>str;
    in[0]=true;
    str.push(0);
    while(!str.empty())
    {
        int x=str.front();
        str.pop();
        in[x]=false;//cout<<x<<endl;
        for(int i=1;i<=n;++i)
        {
            if(flow[x][i]>0&&dist[i]>dist[x]+pay[x][i])
            {
                dist[i]=dist[x]+pay[x][i];//每次只计算一个流的花费 流不会太多 所以时间没问题 
                f[i]=x;
                if(in[i]==false)
                {
                    in[i]=true;
                    str.push(i);
                }
            }
        }
    }//cout<<dist[n]<<endl;
    if(dist[n]==M)
    return 0;
    int k=n;
    while(k!=0)
    {
        int pre=f[k];
        flow[pre][k]--;//只计算了一个流的花费 所以也个更新一个流
        flow[k][pre]++;
        k=pre;
    }
    return dist[n];

}
int Addpay(int n,int m,int k)
{
    memset(flow,0,sizeof(flow));
    memset(pay,0,sizeof(pay));
    for(int i=1;i<=m;++i)//对超级源点到供应者的流进行限制
    {
        flow[0][i]=have[i][k];
    }
    int sum=0;
    for(int i=1;i<=n;++i)//对需求者到超级终极进行流的限制
    {
        flow[i+m][n+m+1]=need[i][k];
        sum=sum+need[i][k];
    }
    for(int i=1;i<=m;++i)
    {
        for(int j=1;j<=n;++j)
        {
            flow[i][j+m]=min(have[i][k],need[j][k]);//对供应者到需求者之间的流进行限制
            pay[i][j+m]=goodpay[k][i][j];//花费统计
            pay[j+m][i]=-pay[i][j+m];//反向花费取负
        }
    }
    int MIN=0;//总花费统计
    int X=0;
    while(1)
    {
        int k=Spfa(n+m+1);
        if(k==0)
        break ;
        MIN+=k;
        X=X+1;//流每次加一
    }
    if(X==sum)//总流是否满足总需求流的量
    return MIN;
    return -1;
}
int main()
{
    int n,m,k;
    while(scanf("%d %d %d",&n,&m,&k)!=EOF)
    {
        if(n==0&&m==0&&k==0)
        break;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=k;++j)
            {
                scanf("%d",&need[i][j]);
            }
        }
        for(int i=1;i<=m;++i)
        {
            for(int j=1;j<=k;++j)
            {
                scanf("%d",&have[i][j]);
            }
        }
        for(int l=1;l<=k;++l)
        {
            for(int i=1;i<=n;++i)
            {
                for(int j=1;j<=m;++j)
                {
                    scanf("%d",&goodpay[l][j][i]);
                }
            }
        }
        int ans=0;
        for(int i=1;i<=k;++i)
        {
            int q=Addpay(n,m,i);//如果哪次物品没满足需求直接-1
            if(q==-1)
            {
                ans=-1;break;
            }
            else
            {
                ans=ans+q;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}