「网络流24题」分配问题
题目描述 Description
有n件工作要分配给n个人做。第i 个人做第j 件工作产生的效益为ij c 。试设计一个将
n件工作分配给n个人做的分配方案,使产生的总效益最大。
«编程任务:
对于给定的n件工作和n个人,计算最优分配方案和最差分配方案。
输入描述 Input Description
第1 行有1 个正整数n,表示有n件工作要分配给n 个人做。接下来的n 行中,每行有n 个整数 cij ,1≤i≤n,1≤j≤n,表示第i 个人做第j件工作产生的效益为cij
输出描述 Output Description
将计算出的最小总效益和最大总效益输出
样例输入 Sample Input
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
样例输出 Sample Output
5
14
数据范围及提示 Data Size & Hint
把所有人看做二分图中顶点Xi,所有工作看做二分图中顶点Yi,建立附加源S汇T。
1、从S向每个Xi连一条容量为1,费用为0的有向边。
2、从每个Yi向T连一条容量为1,费用为0的有向边。
3、从每个Xi向每个Yj连接一条容量为无穷大,费用为Cij的有向边。
求最小费用最大流,最小费用流值就是最少运费,求最大费用最大流,最大费用流值就是最多运费。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include<iostream> #include<cstring> #include<cstdio> #define inf 0x7fffffff #define T 2001 using namespace std; int n,head[2005],q[2005],dis[2005],from[2005],a[1005],mp[1001][1001],cnt,ans; bool inq[2005]; struct data{int from,to,next,v,c;}e[100001]; void ins(int u,int v,int w,int c) { cnt++; e[cnt].from=u;e[cnt].to=v; e[cnt].v=w;e[cnt].c=c; e[cnt].next=head[u];head[u]=cnt; } void insert(int u,int v,int w,int c) {ins(u,v,w,c);ins(v,u,0,-c);} bool spfa() { for(int i=0;i<=T;i++)dis[i]=inf; int t=0,w=1,i,now; dis[0]=q[0]=0;inq[0]=1; while(t!=w) { now=q[t];t++;if(t==2001)t=0; for(int i=head[now];i;i=e[i].next) { if(e[i].v&&dis[e[i].to]>dis[now]+e[i].c) { from[e[i].to]=i; dis[e[i].to]=dis[now]+e[i].c; if(!inq[e[i].to]) { inq[e[i].to]=1; q[w++]=e[i].to; if(w==2001)w=0; } } } inq[now]=0; } if(dis[T]==inf)return 0;return 1; } void mcf() { int i,x=inf; i=from[T]; while(i) { x=min(e[i].v,x); i=from[e[i].from]; } i=from[T]; while(i) { e[i].v-=x; e[i^1].v+=x; ans+=x*e[i].c; i=from[e[i].from]; } } void build(int k) { cnt=1;memset(head,0,sizeof(head));ans=0; for(int i=1;i<=n;i++)insert(0,i,1,0); for(int i=1;i<=n;i++)insert(n+i,T,1,0); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) insert(i,j+n,1,k*mp[i][j]); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&mp[i][j]); build(1); while(spfa())mcf(); printf("%d\n",ans); build(-1); while(spfa())mcf(); printf("%d",-ans); return 0; } |
Subscribe