| Time Limit: 4000MS | Memory Limit: 65536K | |
| Total Submissions: 13242 | Accepted: 4500 |
Description
Input
Output
Sample Input
1 3 3 1 1 1 0 1 1 1 2 2 1 0 1 1 2 3 1 1 1 2 1 1 1 1 1 3 2 20 0 0 0
Sample Output
4 -1
题意：n个客户，m个仓库，l件物品。
n行l列 表示n个客户对l件物品的需求量
m行l列 表示m个仓库对l件物品的的供给量
l行 表示l个物品从i仓库到j客户的一个物品的运费价格
判断是否可以满足客户需求，如果满足求出最小的运费。
思路：最小费用最大流问题
将l件物品分开求最小费用然后相加。
对每个仓库是一个结点，每个客户也是一个结点，除此之外再加上s源点和t结束点
代码（附解释）如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define min(a,b) a<b?a:b
#define N 130
#define INF 999999
int need[N][N],offer[N][N],sum_need[N],sum_offer[N];
int map[N][N],cost[N][N];
int n,m,l;
int pre[N];
int s,t; //源点和汇点
int spfa()
{
int dis[N],vis[N];
int i;
queue<int>q;
for(i=0; i<=t; i++)
dis[i]=INF;
memset(vis,0,sizeof(vis));
vis[s]=1;
dis[s]=0;
q.push(s);
while(!q.empty())
{
int k=q.front();
q.pop();
vis[k]=0;
for(i=0; i<=t; i++)
{
if(map[k][i] && dis[i]>dis[k]+cost[k][i])
{
dis[i]=dis[k]+cost[k][i];
pre[i]=k;
if(vis[i]==0)
{
vis[i]=1;
q.push(i);
}
}
}
}
if(dis[t]!=INF)
return 1;
else
return 0;
}
int fond()
{
int i,j;
int Min=INF;
j=0;
while(spfa())
{
for(i=t;i!=s; i=pre[i])
Min=min(Min,map[pre[i]][i]);
for(i=t; i!=s; i=pre[i])
{
map[pre[i]][i]-=Min;
map[i][pre[i]]+=Min;
j+=cost[pre[i]][i]*Min;
}
}
return j;
}
int main()
{
int i,j,k,sum,sign;
while(scanf("%d%d%d",&n,&m,&l)) // n个客户，m个仓库，l件物品
{
if(n==0 && m==0 && l==0) break;
sum=0;
memset(sum_need,0,sizeof(sum_need));
memset(sum_offer,0,sizeof(sum_offer));
for(i=1; i<=n; i++) //求客户对物品总的需求量
for(j=1; j<=l; j++)
{
scanf("%d",&need[i][j]);
sum_need[j]+=need[i][j];
}
for(i=1;i<=m;i++) //求仓库对物品总的供给量
for(j=1;j<=l;j++)
{
scanf("%d",&offer[i][j]);
sum_offer[j]+=offer[i][j];
}
sign=0;
for(i=1;i<=l;i++)
if(sum_offer[i]<sum_need[i]) //供给小于需求
{
sign=1;
break;
}
s=0; // 源点
t=m+n+1; // 汇点(把客户和仓库都看成节点)
for(k=1;k<=l;k++) // 把l件物品分开计算
{
for(i=0;i<=t; i++)
for(j=0;j<=t;j++)
map[i][j]=cost[i][j]=0; //初始化 节点是0,1,2....,n
for(i=1+m;i<=n+m;i++)
for(j=1;j<=m;j++) // 注意 把客户节点是m+1,m+2,....,m+n
{
scanf("%d",&cost[j][i]);
cost[i][j]=-cost[j][i]; //注意反向
}
if(sign==1) continue;
for(i=1;i<=m;i++)
map[s][i]=offer[i][k]; // 源点s到仓库的边权值为仓库的供给量
for(i=1;i<=m; i++)
for(j=1+m; j<=n+m; j++)
map[i][j]=offer[i][k]; //仓库到客户的的边权值为客户的需求量
for(i=m+1; i<=m+n; i++)
map[i][t]=need[i-m][k]; //客户到汇点t的边权值为客户的需求量
sum+=fond(); // 对k件物品从仓库到客户的最小费用求和
}
if(sign==1)
printf("-1\n");
else
printf("%d\n",sum);
}
return 0;
}
poj 2516 Minimum Cost,布布扣,bubuko.com
原文：http://blog.csdn.net/fyxz1314/article/details/38064013