fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. struct network_flow{
  6.     int max_v,e,s,t,head,tail;
  7.     int *cap,*to,*next,*last,*dist,*q,*now;
  8.  
  9.     network_flow(){}
  10.  
  11.     network_flow(int v, int max_e){
  12.         max_v = v; e = 0;
  13.         cap = new int[2*max_e], to = new int[2*max_e], next = new int[2*max_e];
  14.         last = new int[max_v], q = new int[max_v], dist = new int[max_v], now = new int[max_v];
  15.         fill(last,last+max_v,-1);
  16.     }
  17.  
  18.     void clear(){
  19.         fill(last,last+max_v,-1);
  20.         e = 0;
  21.     }
  22.  
  23.     void add_edge(int u, int v, int uv, int vu = 0){
  24.         to[e] = v, cap[e] = uv, next[e] = last[u]; last[u] = e++;
  25.         to[e] = u, cap[e] = vu, next[e] = last[v]; last[v] = e++;
  26.     }
  27.  
  28. 	bool bfs(){
  29. 		fill(dist,dist+max_v,-1);
  30. 		head = tail = 0;
  31.  
  32. 		q[tail] = t; ++tail;
  33. 		dist[t] = 0;
  34.  
  35. 		while(head<tail){
  36. 			int v = q[head]; ++head;
  37.  
  38. 			for(int er = last[v];er!=-1;er = next[er]){
  39. 				if(cap[er^1]>0 && dist[to[er]]==-1){
  40. 					q[tail] = to[er]; ++tail;
  41. 					dist[to[er]] = dist[v]+1;
  42. 				}
  43. 			}
  44. 		}
  45.  
  46. 		return dist[s]!=-1;
  47. 	}
  48.  
  49. 	int dfs(int v, int f){
  50. 		if(v==t) return f;
  51.  
  52. 		for(int &er = now[v];er!=-1;er = next[er]){
  53. 			if(cap[er]>0 && dist[to[er]]==dist[v]-1){
  54. 				int ret = dfs(to[er],min(f,cap[er]));
  55.  
  56. 				if(ret>0){
  57. 					cap[er] -= ret;
  58. 					cap[er^1] += ret;
  59. 					return ret;
  60. 				}
  61. 			}
  62. 		}
  63.  
  64. 		return 0;
  65. 		}
  66.  
  67. 	long max_flow(int source, int sink){
  68. 		s = source; t = sink;
  69. 		long int f = 0,x;
  70.  
  71. 		while(bfs()){
  72. 			for(int i = 0;i<max_v;++i) now[i] = last[i];
  73.  
  74. 			while(true){
  75. 				x = dfs(s,INT_MAX);
  76. 				if(x==0) break;
  77. 				f += x;
  78. 			}
  79. 		}
  80.  
  81. 		return f;
  82. 	}
  83. }graph(402,200*200+400+2);
  84.  
  85. int main() {
  86. 	int t, v,n,x,l,m;
  87. 	scanf("%d",&t);
  88. 	while(t--) {
  89. 		scanf("%d %d %d",&l,&m,&n);
  90. 		graph.clear();
  91. 		for(int i=1;i<=m;i++) {
  92. 			scanf("%d",&x);
  93. 			graph.add_edge(0,i,x);
  94. 		}
  95. 		for(int i=1;i<=n;i++) {
  96. 			scanf("%d",&x);
  97. 			graph.add_edge(m+i,m+n+1,x);
  98. 		}
  99. 		for(int i=1;i<=m;i++) {
  100. 			for(int j=1;j<=n;j++) {
  101. 				scanf("%d",&x);
  102. 				graph.add_edge(i,j+m,x);
  103. 			}
  104. 		}
  105. 		printf("%ld\n",graph.max_flow(0,m+n+1));
  106. 	}
  107. 	return 0;
  108. }
  109.  
  110.  
Runtime error #stdin #stdout 0.01s 4408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/T6fsQv
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!