POJ 2516 Minimum Cost(拆点+KM完备匹配)

题目链接：http://poj.org/problem?id=2516

题目大意：

第一行是N,M,K

接下来N行：第i行有K个数字表示第i个卖场对K种商品的需求情况

接下来M行：第j行有K个数字表示第j个库房对K种商品的存货情况

接下来K个N*M的矩阵：

每个矩阵(i,j)表示第k种商品从第j个库房运到第i个卖场的运费（单价）

求满足所有需求的最小花费，如果不能全部满足输出-1。

解题思路：

拆点，对于第k种商品有：

把每个卖场的需求按件数拆成各个小点（比如需要x件就看做x个点）

把每个库房的存货量按件数拆成各个小点（同上）

然后以运费为权值连边（单向边）

做K次完备匹配即可。

代码：

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cstring>
  6 using namespace std;
  7 const int N=55;
  8 const int M=205;
  9 const int INF=0x3f3f3f3f;
 10 
 11 int nx,ny,d;
 12 int offer[N][N],need[N][N],cost[N][N][N];//cost[k][i][j]表示将第k件物品从供应商j送到老板i的花费
 13 int lx[M],ly[M],link[M],g[M][M],belongA[M],belongB[M];
 14 bool visx[M],visy[M];
 15 
 16 bool dfs(int x){
 17     visx[x]=true;
 18     for(int y=0;y<ny;y++){
 19         if(visy[y]||!g[x][y]) continue;
 20         int tmp=lx[x]+ly[y]-g[x][y];
 21         if(tmp==0){
 22             visy[y]=true;
 23             if(link[y]==-1||dfs(link[y])){
 24                 link[y]=x;
 25                 return true;
 26             }
 27         }
 28         else d=min(d,tmp);
 29     }
 30     return false;
 31 }
 32 
 33 int KM(){
 34     memset(link,-1,sizeof(link));
 35     memset(ly,0,sizeof(ly));
 36     for(int i=0;i<nx;i++){
 37         lx[i]=-INF;
 38         for(int j=0;j<ny;j++){
 39             if(g[i][j]>lx[i])
 40                 lx[i]=g[i][j];
 41         }
 42     }
 43     for(int x=0;x<nx;x++){
 44         while(true){
 45             memset(visx,false,sizeof(visx));
 46             memset(visy,false,sizeof(visy));
 47             d=INF;
 48             if(dfs(x)) break;
 49             for(int i=0;i<nx;i++){
 50                 if(visx[i])
 51                     lx[i]-=d;
 52             }
 53             for(int i=0;i<ny;i++){
 54                 if(visy[i])
 55                     ly[i]+=d;
 56             }
 57         }
 58     }
 59     int ans=0;
 60     for(int i=0;i<ny;i++){
 61         if(link[i]!=-1){
 62             ans+=g[link[i]][i];
 63         }
 64     }
 65     return ans;
 66 }
 67 
 68 int main(){
 69     int n,m,k;
 70     while(~scanf("%d%d%d",&n,&m,&k)){
 71         if(n==0&&m==0&&k==0) break;
 72         for(int i=0;i<n;i++){
 73             for(int j=0;j<k;j++){
 74                 scanf("%d",&need[i][j]);
 75             }
 76         }
 77         for(int i=0;i<m;i++){
 78             for(int j=0;j<k;j++){
 79                 scanf("%d",&offer[i][j]);
 80             }
 81         }
 82         for(int t=0;t<k;t++){
 83             for(int i=0;i<n;i++){
 84                 for(int j=0;j<m;j++)
 85                     scanf("%d",&cost[t][i][j]);
 86             }
 87         }
 88         bool flag=true;
 89         //首先对于一种商品，如果这种所有的存货不足需求就直接输出-1
 90         for(int t=0;t<k;t++){
 91             int sum1=0,sum2=0;
 92             for(int i=0;i<n;i++){
 93                 sum1+=need[i][t];
 94             }
 95             for(int i=0;i<m;i++){
 96                 sum2+=offer[i][t];
 97             }
 98             if(sum1>sum2){
 99                 flag=false;
100                 break;
101             }
102         }
103         if(!flag){
104             puts("-1");
105             continue;
106         }
107         int ans=0;
108         for(int t=0;t<k;t++){
109             int cntA=0,cntB=0;
110             //拆点，
111             for(int i=0;i<n;i++){
112                 for(int j=0;j<need[i][t];j++){
113                     belongA[cntA++]=i;
114                 }
115             }
116             for(int i=0;i<m;i++){
117                 for(int j=0;j<offer[i][t];j++){
118                     belongB[cntB++]=i;
119                 }
120             }
121             for(int i=0;i<cntA;i++){
122                 for(int j=0;j<cntB;j++){
123                     g[i][j]=-cost[t][belongA[i]][belongB[j]];
124                 }
125             }
126             nx=cntA,ny=cntB;
127             ans+=KM();
128         }
129         printf("%d
",-ans);
130     }
131     return 0;
132 }