【网络流24题-18】分配问题网络流费用流

2019-11-08 01:30:29

字体：大中小

来源：转载

供稿：网友

题目描述

　　有n件工作要分配给n（n<=100）个人做。第i个人做第 j件工作产生的效益为cij。试设计一个将n件工作分配给n个人做的分配方案，使产生的总效益最大。对于给定的n件工作和 n个人，计算最优分配方案和最差分配方案。

题目大意

　　见题目描述~~A.A~~

数据范围

　　见题目描述~~A.A~~

样例输入

5 2 2 2 1 2 2 3 1 2 4 2 0 1 1 1 2 3 4 3 3 3 2 1 2 1

样例输出

5 14

解题思路

　　S点向人连边，权值为1，费用为0，人向物品连边，权值为1，费用为Cij，物品向T连边，权值为1，费用为0。　　最小效益则为最小费用流，最大收益为最大费用流（关于最大费用流的问题，我是将费用取反，最后的答案也取反，当然也可以SPFA求最长路）。

代码

#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>#include <queue>#define Maxn 23333#define Maxe 23333using namespace std;inline int Getint(){int x=0,f=1;char ch=getchar();while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}int n,cnt=0,S,T,h1[Maxn],h2[Maxn],dis[Maxn],PRe[Maxn],preto[Maxn],vis[Maxn];struct node{int to,next,v,k,pair;}e1[Maxe],e2[Maxe];//e1,h1为求最小费用流，e2,h2为求最大费用流void AddEdge(node *e,int h[],int x,int y,int v,int k,int pair){e[cnt]=(node){y,h[x],v,k,pair};h[x]=cnt;}void AddEdge(node *e,int h[],int x,int y,int v,int k){AddEdge(e,h,x,y,v,k,++cnt+1);AddEdge(e,h,y,x,0,-k,++cnt-1);}void Init(){ n=Getint(); S=0,T=n+n+1; int t; for(int i=1;i<=n;i++){ AddEdge(e1,h1,S,i,1,0); AddEdge(e2,h2,S,i,1,0); for(int j=1;j<=n;j++) AddEdge(e1,h1,i,j+n,1,t=Getint()),AddEdge(e2,h2,i,j+n,1,-t);//建边，e2的费用取反 } for(int j=1;j<=n;j++) AddEdge(e1,h1,j+n,T,1,0),AddEdge(e2,h2,j+n,T,1,0);}bool SPFA(node *e,int h[]){ queue<int>Q; memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(pre,0,sizeof(pre)); dis[S]=0; vis[S]=1; Q.push(S); while(Q.size()){ int x=Q.front(); Q.pop(); vis[x]=false; for(int p=h[x];p;p=e[p].next){ int y=e[p].to; if(e[p].v&&dis[y]>dis[x]+e[p].k){ pre[y]=p; preto[y]=x; dis[y]=dis[x]+e[p].k; if(!vis[y])Q.push(y); } } } return dis[T]<=(1<<29);}void Adjust(node *e,int &Ans){ int flow=1<<30; for(int p=T;p!=S;p=preto[p]) flow=min(flow,e[pre[p]].v); for(int p=T;p!=S;p=preto[p]){ e[pre[p]].v-=flow; e[e[pre[p]].pair].v+=flow; } Ans+=dis[T]*flow;}int main(){ int Ans1=0,Ans2=0; Init(); while(SPFA(e1,h1))Adjust(e1,Ans1); cout<<Ans1<<"/n"; while(SPFA(e2,h2))Adjust(e2,Ans2); cout<<-Ans2;//答案也取反 return 0;}

上一篇：QT Demo 之 window

下一篇：ds1302简单解析