首页 > 代码库 > POJ 2516 最小费用流
POJ 2516 最小费用流
依然最小费用最大流模板题
建边麻烦了些
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <utility>#include <stack>#include <queue>#include <map>#include <deque>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define INF 0x3f3f3f3f#define MAXM 3005#define MAXN 300using namespace std;struct Edge{ int y,c,w,ne;}e[MAXM*4];int all,be[MAXN],n,m,k,x,y,w,ans,Mincost,Maxflow,s,t,q[MAXM*4];int supply[MAXN][MAXN],need[MAXN][MAXN];int pre[MAXN],dis[MAXN];bool vis[MAXN];void init(){ all=0; memset(be,-1,sizeof(be));}void add(int x, int y, int c, int w){ e[all].y=y;e[all].c=c;e[all].w=w; e[all].ne=be[x]; be[x]=all++; e[all].y=x;e[all].c=0;e[all].w=-w; e[all].ne=be[y]; be[y]=all++;}bool spfa(int s, int t){ queue<int> q; for(int i=0; i<n+m+2; i++) { dis[i]=INF; vis[i]=0; pre[i]=-1; } dis[s]=0; vis[s]=1; q.push(s); while(!q.empty()) { int u=q.front(); vis[u]=0; q.pop(); for(int i=be[u]; i!=-1; i=e[i].ne) { int v=e[i].y; if(e[i].c && dis[v]>dis[u]+e[i].w) { dis[v]=dis[u]+e[i].w; pre[v]=i; if(!vis[v]) { vis[v]=1; q.push(v); } } } } if(pre[t]==-1) return 0; return 1;}void MincostMaxflow(int s, int t){ Mincost=Maxflow=0; while(spfa(s,t)) { int minc=INF; for(int i=pre[t]; i!=-1; i=pre[e[i^1].y]) if(minc>e[i].c) minc=e[i].c; for(int i=pre[t]; i!=-1; i=pre[e[i^1].y]) { e[i].c-=minc; e[i^1].c+=minc; Mincost+=e[i].w*minc; } Maxflow+=minc; }}int main(){ while(scanf("%d%d%d",&n,&m,&k)!=EOF && n && m && k) { for(int i=0; i<n; i++) for(int j=0; j<k; j++) scanf("%d",&need[i][j]); for(int i=0; i<m; i++) for(int j=0; j<k; j++) scanf("%d",&supply[i][j]); s=m+n; t=m+n+1; bool flag=1; ans=0; for(int tk=0; tk<k; tk++) { init(); for(int i=0; i<n; i++) for(int j=0; j<m; j++) { scanf("%d",&w); add(j,i+m,INF,w); } if(flag) { for(int i=0; i<m; i++) add(s,i,supply[i][tk],0); for(int i=0; i<n; i++) add(m+i,t,need[i][tk],0); MincostMaxflow(s,t); for(int i=be[t]; i!=-1; i=e[i].ne) if(e[i^1].c>0) flag=0; if(flag) ans+=Mincost; } } if(!flag) printf("-1\n"); else printf("%d\n",ans); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。