POJ2516 Minimum Cost
2024-09-04 22:51:46
亲爱的,一个货物销售者,现在遇到了一个大问题,他需要你的帮助。在他的销售区域有 N 个店主(从 1 到 N)向他储存货物,Dearboy 有M 个供应点(从 1 到 M),每个供应点提供 K 种不同的货物(从 1 到K)。一旦店主订购货物,迪尔博伊应该安排哪个供应点向店主提供多少货物,以降低总的运输成本。众所周知,从不同的货源地向不同的店主运送不同种类的一件商品的成本可能是不同的。考虑到每个货源地存放的 K 种货物,N 个店主订购的K 种货物,以及从不同货源地向不同店主运送不同种类货物的成本,您应该说明如何安排货物的供应,以使运输总成本最小化。
最小费用最大流模板~
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=;
const int inf=1e9;
int cap[maxn][maxn];
int flow[maxn][maxn];
int cost[maxn][maxn];
int n;
int f;//最大流
int c;//最小费用
int st,ed;
bool visit[maxn];
int pre[maxn],dist[maxn];
bool spfa () {
queue<int> q;
for (int u=;u<=n;u++) {
if (u==st) {
q.push(u);
dist[u]=;
visit[u]=true;
}
else {
dist[u]=inf;
visit[u]=false;
}
}
while (!q.empty()) {
int u=q.front();
visit[u]=false;
q.pop();
for (int v=;v<=n;v++) {
if (cap[u][v]>flow[u][v]&&dist[v]>dist[u]+cost[u][v]) {
dist[v]=dist[u]+cost[u][v];
pre[v]=u;
if (!visit[v]) {
visit[v]=true;
q.push(v);
}
}
}
}
if (dist[ed]>=inf) return false;
return true;
}
void minCostMaxflow () {
memset (flow,,sizeof(flow));
c=f=;
while (spfa()) {
int Min=inf;
for (int u=ed;u!=st;u=pre[u])
Min=min(Min,cap[pre[u]][u]-flow[pre[u]][u]);
for (int u=ed;u!=st;u=pre[u]) {
flow[pre[u]][u]+=Min;
flow[u][pre[u]]-=Min;
}
c+=dist[ed]*Min;
f+=Min;
}
}
int order[maxn][maxn];
int supply[maxn][maxn];
int tolorder[maxn];
int main() {
int N,M;
int K;
while(scanf("%d%d%d",&N,&M,&K)!=EOF) {
if(N==&&M==&&K==)break;
st=;
n=N+M+;
ed=n;
memset(cap,,sizeof(cap));
memset(cost,,sizeof(cost));
for(int i=;i<N;i++)
for(int j=;j<K;j++)
scanf("%d",&order[i][j]);
for(int i=;i<M;i++)
for(int j=;j<K;j++)
scanf("%d",&supply[i][j]);
for(int i=;i<K;i++) {
tolorder[i]=;
for(int j=;j<N;j++)
tolorder[i]+=order[j][i];
}
for(int i=;i<=M;i++)
for(int j=M+;j<=N+M;j++)
cap[i][j]=inf;
bool flag=true;
int ans=;
for(int i=;i<K;i++) {
for(int j=M+;j<=M+N;j++)
for(int k=;k<=M;k++) {
scanf("%d",&cost[k][j]);
cost[j][k]=-cost[k][j];
}
if(!flag)continue;
for(int j=;j<=M;j++)
cap[st][j]=supply[j-][i];
for(int j=;j<=N;j++)
cap[j+M][ed]=order[j-][i];
minCostMaxflow();
if(f<tolorder[i])flag=false;
else ans+=c;
}
if(!flag)printf("-1\n");
else printf("%d\n",ans);
}
return ;
}
最新文章
- AC日记——蓬莱山辉夜 codevs 2830
- google软件测试之道--读后笔记
- 【译】用boosting构建简单的目标分类器
- Python错误、调试和测试
- Summary Ranges
- POJ 3461 Oulipo(乌力波)
- windows下安装php5.2.*,php5.3.*,php5.4.*版本的memcache扩展(转)
- LCIS(线段树区间合并)
- Android - 用Fragments实现动态UI - 创建Fragment
- ES 6 : 字符串的扩展
- StackExchange.Redis学习笔记(三)
- SQL Count(*)函数,GROUP_By,Having的联合使用
- jmeter远程分布执行遇到的网卡坑(A Test is currently running,stop or ....)
- Sql Server 2012 集群配置
- 把ajax包装成promise的形式(1)
- nginx 目录讲解
- 【Zookeeper系列】ZooKeeper安装配置(转)
- linux终端神器kmux
- JS-获取任意html节点属性
- 软工实践-Alpha 冲刺 (9/10)