首页 > 代码库 > POJ 2516 跑k次的最小费用最大流
POJ 2516 跑k次的最小费用最大流
题目大意:给出n个客户对k个商品的需求量,又给出m个仓库对k个物品的存货量以及对k个物品从i仓库到j客户的一个物品的运费价格,让判断是否可以满足客户需求,然后就是如果满足求出最小的运费,是典型的最小费用最大流!
思路:可以将k中物品分开求最小费用最大流,然后想加得到总的最小费用最大流!
建图,对每个仓库是一个结点,每个客户也是一个结点,除此之外再加上s源点和t结束点!
1、s到仓库i的边的流量为仓库i的供给量,费用没有当然为0;
2、仓库i到客户j的流量为仓库的供给量,费用为仓库i到客户j的运输费用;
3、客户j到t的流量为客户的需求量,费用没有当然也为0;
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #include<set> #include<cmath> #include<bitset> #define mem(a,b) memset(a,b,sizeof(a)) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define llson j<<1,l,mid #define rrson j<<1|1,mid+1,r #define INF 0x7fffffff typedef long long ll; typedef unsigned long long ull; using namespace std; #define maxn 20005 struct { int v,w,c,next,re; //re记录逆边的下标,c是费用,w是流量 } e[maxn]; int n,cnt; int head[maxn],que[maxn*8],pre[maxn],dis[maxn]; bool vis[maxn]; void add(int u, int v, int w, int c) { e[cnt].v=v,e[cnt].w=w,e[cnt].c=c; e[cnt].next=head[u]; e[cnt].re=cnt+1,head[u]=cnt++; e[cnt].v=u,e[cnt].w=0,e[cnt].c=-c; e[cnt].next=head[v]; e[cnt].re=cnt-1,head[v]=cnt++; } bool spfa() { int i, l = 0, r = 1; for(i = 0; i <= n; i ++) dis[i] = INF,vis[i] = false; dis[0]=0,que[0]=0,vis[0]=true; while(l<r) { int u=que[l++]; for(i=head[u];i!=-1;i=e[i].next) { int v = e[i].v; if(e[i].w&&dis[v]>dis[u]+e[i].c) { dis[v] = dis[u] + e[i].c; pre[v] = i; if(!vis[v]) { vis[v] = true; que[r++] = v; } } } vis[u] = false; } return dis[n]!=INF; } int change() { int i,p,sum=INF,ans=0; for(i=n;i!=0;i=e[e[p].re].v) {//e[e[p].re].v为前向结点,不理解看add和spfa p=pre[i];//p为前向结点编号 sum=min(sum,e[p].w); } for(i=n;i!=0;i=e[e[p].re].v) { p=pre[i]; e[p].w-=sum; e[e[p].re].w+=sum; ans+=sum*e[p].c;//c记录的为单位流量费用,必须得乘以流量。 } return ans; } int EK() { int sum=0; while(spfa()) sum+=change(); return sum; } void init() { mem(head,-1),mem(pre,0),cnt=0; } int a[51][51],b[51][51],cost[51][101],aa[51],bb[51]; int main() { //freopen("1.txt","r",stdin); int N,m,K; while(~scanf("%d%d%d",&N,&m,&K)) { if(!N&&!m&&!K) break; int i,j,k,flag=0,sum=0,s=0,t=m+N+1; mem(aa,0),mem(bb,0); for(i=1;i<=N;i++) for(j=1;j<=K;j++) { scanf("%d",&a[i][j]); aa[j]+=a[i][j]; } for(i=1;i<=m;i++) for(j=1;j<=K;j++) { scanf("%d",&b[i][j]); bb[j]+=b[i][j]; } for(i=1;i<=K;i++) if(bb[i]<aa[i]) {flag=1;break;} for(k=1;k<=K;k++) { for(i=m+1;i<=N+m;i++) for(j=1;j<=m;j++) scanf("%d",&cost[j][i]); if(flag) continue; init(); for(i=1;i<=m;i++) add(s,i,b[i][k],0); for(i=1;i<=m;i++) for(j=m+1;j<=N+m;j++) add(i,j,b[i][k],cost[i][j]); for(i=m+1;i<=m+N;i++) add(i,t,a[i-m][k],0); n=t; sum+=EK();//每种k物品都求一次 } if(flag) puts("-1"); else printf("%d\n",sum); } return 0; }
POJ 2516 跑k次的最小费用最大流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。