首页 > 代码库 > POJ 2516 Minimum Cost(网络流之费用流)
POJ 2516 Minimum Cost(网络流之费用流)
题目地址:POJ 2516
我晕啊。。。这题一上来就想到了对每种货物分开求。。但是马上就放弃了。。感觉这样求50次费用流太耗时。。后来就果断拆点,拆了好长时间,一直TLE。。即使降到了2600个点也TLE。。然后又想起了这个分开求的方法,又突然觉得100个点的费用流几乎不费什么时间。。最多也只是求50次而已,还是可以试试的。。于是一试居然还真过了。。。
说到这里,思路应该已经知道了吧。就是对每种货物分开求,因为每种货物是相互独立的。每一次的建图思路就是:
源点与供应商连边,流量权值为供应商这种货物的供应量,费用权值为0,汇点与店家连边,流量权值为店家所需要的这种货物的量,费用权值为0。然后供应商与相应的店家相连,费用权值为相应的输入的值,流量权值为INF。
代码如下:
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include <set> #include <algorithm> using namespace std; const int INF=0x3f3f3f3f; const int maxn=300; int head[maxn], source, sink, cnt, flow, cost, sum, mpn[60][60], mpm[60][60]; int d[maxn], vis[maxn], cur[maxn], f[maxn]; struct node { int u, v, cap, cost, next; } edge[3000000]; void add(int u, int v, int cap, int cost) { edge[cnt].v=v; edge[cnt].cap=cap; edge[cnt].cost=cost; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].v=u; edge[cnt].cap=0; edge[cnt].cost=-cost; edge[cnt].next=head[v]; head[v]=cnt++; } int spfa() { memset(vis,0,sizeof(vis)); memset(d,INF,sizeof(d)); deque<int>q; q.push_back(source); d[source]=0; cur[source]=-1; f[source]=INF; while(!q.empty()) { int u=q.front(); q.pop_front(); vis[u]=0; for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(d[v]>d[u]+edge[i].cost&&edge[i].cap) { d[v]=d[u]+edge[i].cost; f[v]=min(f[u],edge[i].cap); cur[v]=i; if(!vis[v]) { if(!q.empty()&&d[v]<d[q.front()]) { q.push_front(v); } else q.push_back(v); vis[v]=1; } } } } if(d[sink]==INF) return 0; flow+=f[sink]; cost+=d[sink]*f[sink]; for(int i=cur[sink]; i!=-1; i=cur[edge[i^1].v]) { edge[i].cap-=f[sink]; edge[i^1].cap+=f[sink]; } return 1; } int mcmf() { flow=cost=0; while(spfa()) ; if(flow<sum) return -1; else return cost; } int main() { int n, m, k, i, j, x, h, ans, flag; while(scanf("%d%d%d",&n,&m,&k)!=EOF&&n&&m&&k) { ans=0; flag=0; source=0; sink=n+m+1; for(i=1; i<=n; i++) { for(j=1; j<=k; j++) { scanf("%d",&mpn[i][j]); } } for(i=1; i<=m; i++) { for(j=1; j<=k; j++) { scanf("%d",&mpm[i][j]); } } for(h=1; h<=k; h++) { memset(head,-1,sizeof(head)); cnt=0; sum=0; for(i=1; i<=n; i++) { add(i+m,sink,mpn[i][h],0); sum+=mpn[i][h]; for(j=1;j<=m;j++) { scanf("%d",&x); add(j,i+m,INF,x); } } if(flag) continue ; for(i=1;i<=m;i++) { add(source,i,mpm[i][h],0); } int y=mcmf(); //printf("%d\n",y); if(y==-1) { flag=1; } else ans+=y; } if(flag) printf("-1\n"); else printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。