Minimum Cost(最小费用最大流,好题)
Minimum Cost
http://poj.org/problem?id=2516
Time Limit: 4000MS | Memory Limit: 65536K | |
Total Submissions: 19019 | Accepted: 6716 |
Description
It's known that the cost to transport one unit goods for different kinds from different supply places to different shopkeepers may be different. Given each supply places' storage of K kinds of goods, N shopkeepers' order of K kinds of goods and the cost to transport goods for different kinds from different supply places to different shopkeepers, you should tell how to arrange the goods supply to minimize the total cost of transport.
Input
Then come K integer matrices (each with the size N * M), the integer (this integer is belong to (0, 100)) at the i-th row, j-th column in the k-th matrix represents the cost to transport one unit of k-th goods from the j-th supply place to the i-th shopkeeper.
The input is terminated with three "0"s. This test case should not be processed.
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
Source
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std; const int INF=0x3f3f3f3f;
const int N=;
const int M=;
int top;
int dist[N],pre[N];
bool vis[N];
int c[N];
int maxflow; struct Vertex{
int first;
}V[N];
struct Edge{
int v,next;
int cap,flow,cost;
}E[M]; void init(){
memset(V,-,sizeof(V));
top=;
maxflow=;
} void add_edge(int u,int v,int c,int cost){
E[top].v=v;
E[top].cap=c;
E[top].flow=;
E[top].cost=cost;
E[top].next=V[u].first;
V[u].first=top++;
} void add(int u,int v,int c,int cost){
add_edge(u,v,c,cost);
add_edge(v,u,,-cost);
} bool SPFA(int s,int t,int n){
int i,u,v;
queue<int>qu;
memset(vis,false,sizeof(vis));
memset(c,,sizeof(c));
memset(pre,-,sizeof(pre));
for(i=;i<=n;i++){
dist[i]=INF;
}
vis[s]=true;
c[s]++;
dist[s]=;
qu.push(s);
while(!qu.empty()){
u=qu.front();
qu.pop();
vis[u]=false;
for(i=V[u].first;~i;i=E[i].next){
v=E[i].v;
if(E[i].cap>E[i].flow&&dist[v]>dist[u]+E[i].cost){
dist[v]=dist[u]+E[i].cost;
pre[v]=i;
if(!vis[v]){
c[v]++;
qu.push(v);
vis[v]=true;
if(c[v]>n){
return false;
}
}
}
}
}
if(dist[t]==INF){
return false;
}
return true;
} int MCMF(int s,int t,int n){
int d;
int i,mincost;
mincost=;
while(SPFA(s,t,n)){
d=INF;
for(i=pre[t];~i;i=pre[E[i^].v]){
d=min(d,E[i].cap-E[i].flow);
}
maxflow+=d;
for(i=pre[t];~i;i=pre[E[i^].v]){
E[i].flow+=d;
E[i^].flow-=d;
}
mincost+=dist[t]*d;
}
return mincost;
} int seller[][];
int storage[][];
int matrix[][][]; int main(){
int n,m,k;
int v,u,w,c;
int s,t;
while(~scanf("%d %d %d",&n,&m,&k)){
if(!n&&!m&&!k) break;
int sum=;
for(int i=;i<=n;i++){
for(int j=;j<=k;j++){
scanf("%d",&seller[i][j]);
sum+=seller[i][j];
}
}
for(int i=;i<=m;i++){
for(int j=;j<=k;j++){
scanf("%d",&storage[i][j]);
}
}
for(int i=;i<=k;i++){
for(int j=;j<=n;j++){
for(int w=;w<=m;w++){
scanf("%d",&matrix[i][j][w]);
}
}
}
s=,t=n+m+;
int ANS=;
int flow=;
for(int i=;i<=k;i++){
init();
for(int j=;j<=n;j++){
add(s,j,seller[j][i],);
}
for(int j=;j<=n;j++){
for(int w=;w<=m;w++){
add(j,n+w,storage[w][i],matrix[i][j][w]);
}
}
for(int j=;j<=m;j++){
add(n+j,t,storage[j][i],);///INF
}
int ans=MCMF(s,t,t+);
ANS+=ans;
flow+=maxflow;
} if(flow==sum) printf("%d\n",ANS);
else printf("-1\n");
}
}
最新文章
- Linux C 文件操作,系统调用 -- open()、read() 和 标准I/O库 -- fopen()、fread()
- macos开发pgsql数据库
- Coursera 机器学习课程 机器学习基础:案例研究 证书
- android事件分发机制
- CLR via C#(12)-委托Delegate
- sed 入门
- vue组件,可以通过npm引用的组件
- NLP是什么
- protobuff 编译注意事项
- 论文笔记:A Review on Deep Learning Techniques Applied to Semantic Segmentation
- 通过mapreduce把mysql的一张表的数据导到另外一张表中
- WebDriver高级应用实例(9)
- JavaScript 总结(前端常用工具类的封装)
- 数据库cmd窗口登录
- Windows 消息机制浅析
- 数据库 插入时 碰到NULL报错判断的一种方法(技巧)
- Java 理论与实践: 修复 Java 内存模型,第 2 部分(转载)
- 学习动态性能表(4)--v$sqltext&;v$sqlarea
- FPGA中RAM使用探索
- ubuntu14.04 搭建samba