poj 2516 Minimum Cost

http://poj.org/problem?id=2516
이 문제 와 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
",ans);

    }

    return 0;

}