首页 > 代码库 > [网络流24题] 分配问题

[网络流24题] 分配问题

2024-09-08 08:41:17   219人阅读

740. [网络流24题] 分配问题

★★   输入文件：job.in   输出文件：job.out   简单对比
时间限制：1 s   内存限制：128 MB


«问题描述：

有n件工作要分配给n个人做。第i 个人做第j 件工作产生的效益为ij c 。试设计一个将
n件工作分配给n个人做的分配方案，使产生的总效益最大。

«编程任务：

对于给定的n件工作和n个人，计算最优分配方案和最差分配方案。

«数据输入：

由文件job.in提供输入数据。文件的第1 行有1 个正整数n，表示有n件工作要分配
给n 个人做。接下来的n 行中，每行有n 个整数ij c ，1≤i≤n，1≤j≤n，表示第i 个人做
第j件工作产生的效益为ij c 。

«结果输出:

程序运行结束时，将计算出的最小总效益和最大总效益输出到文件job.out中。
输入文件示例 输出文件示例
job.in

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

job.out

5

14

数据范围

N<=100

分析： 

最小费用最大流和最大费油最大流 的裸题

实现 EK（貌似zkw更优）

显示代码纯文本

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. using namespace std;
  5. const int N=210;
  6. const int inf=2e9;
  7. struct edge{int v,cap,cost,next;}e[N*N*2];int tot=1,head[N];
  8. int n,m,S,T,ans,a[N][N],dis[N],pre[N],q[N*N*2];bool vis[N];
  9. inline int read(){
  10. 	int x=0,f=1;char ch=getchar();
  11. //	while(ch<‘0‘||ch>‘9‘){if(ch=‘-‘)f=-1;ch=getchar();}读入优化写错了,本地没检测出来。。。 
  12. 	while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
  13. 	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
  14. 	return x*f;
  15. }
  16. inline void add(int x,int y,int z,int cost){
  17. 	e[++tot].v=y;e[tot].cap=z;e[tot].cost=cost;e[tot].next=head[x];head[x]=tot;
  18. 	e[++tot].v=x;e[tot].cap=0;e[tot].cost=-cost;e[tot].next=head[y];head[y]=tot;
  19. }
  20. inline bool spfa(int f){
  21. 	if(f)for(int i=S;i<=T;i++) dis[i]=inf,vis[i]=0;//min cost
  22. 	else for(int i=S;i<=T;i++) dis[i]=-inf,vis[i]=0;//max cost
  23. 	unsigned short h=0,t=1;q[t]=S;dis[S]=0;
  24. 	while(h!=t){
  25. 		int x=q[++h];vis[x]=0;
  26. 		for(int i=head[x];i;i=e[i].next){
  27. 			if(e[i].cap&&( (f&&dis[e[i].v]>dis[x]+e[i].cost) 
  28. 						||(!f&&dis[e[i].v]<dis[x]+e[i].cost) )){
  29. 				dis[e[i].v]=dis[x]+e[i].cost;
  30. 				pre[e[i].v]=i;
  31. 				if(!vis[e[i].v]){
  32. 					vis[e[i].v]=1;
  33. 					q[++t]=e[i].v;
  34. 				}
  35. 			}
  36. 		}
  37. 	}
  38. 	if(f) return dis[T]!=inf;
  39. 	else return dis[T]!=-inf;
  40. }
  41. inline int augment(){
  42. 	int flow=inf;
  43. 	for(int i=T;i!=S;i=e[pre[i]^1].v) flow=min(flow,e[pre[i]].cap);
  44. 	for(int i=T;i!=S;i=e[pre[i]^1].v){
  45. 		e[pre[i]].cap-=flow;
  46. 		e[pre[i]^1].cap+=flow;
  47. 	}
  48. 	return dis[T]*flow;
  49. }
  50. inline void init(){
  51. 	n=read();
  52. 	for(int i=1;i<=n;i++){
  53. 		for(int j=1;j<=n;j++){
  54. 			a[i][j]=read();
  55. 		}
  56. 	}
  57. }
  58. inline void mapping(){
  59. 	S=0,T=n<<1|1;
  60. 	tot=1;memset(head,0,sizeof head);
  61. 	for(int i=1;i<=n;i++) add(S,i,1,0);
  62. 	for(int i=1;i<=n;i++) add(i+n,T,1,0);
  63. 	for(int i=1;i<=n;i++){
  64. 		for(int j=1;j<=n;j++){
  65. 			add(i,j+n,1,a[i][j]);
  66. 		}
  67. 	}
  68. }
  69. inline void work(){
  70. 	mapping();
  71. 	while(spfa(1)) ans+=augment();
  72. 	printf("%d\n",ans);
  73. 	mapping();ans=0;
  74. 	while(spfa(0)) ans+=augment();
  75. 	printf("%d\n",ans);
  76. }
  77. int main(){
  78. 	freopen("job.in","r",stdin);
  79. 	freopen("job.out","w",stdout);
  80. 	init();
  81. 	work();
  82. 	return 0;
  83. }

 

[网络流24题] 分配问题


联系
我们