fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <queue>
  4. #include <limits>
  5. #include <algorithm>
  6. using namespace std;
  7. #define inf 1000000000
  8. struct NetworkFlow {
  9. 	struct Edge {
  10. 		int target, inverse_index;
  11. 		int capacity, flow; 
  12. 		Edge(int t, int c, int ii): target(t), capacity(c), flow(0), inverse_index(ii) {}
  13. 		int residual() const { return capacity - flow; }
  14. 	};
  15. 	int V;
  16. 	vector< vector<Edge> > adj;
  17. 	vector<int> levels, edges_tried;
  18.  
  19. 	NetworkFlow(int V): V(V), adj(V), levels(V), edges_tried(V) {}
  20.  
  21. 	void add_edge(int a, int b, int a2b, int b2a=0) {
  22. 		int a2b_index = adj[a].size(), b2a_index = adj[b].size();
  23. 		adj[a].push_back(Edge(b, a2b, b2a_index));
  24. 		adj[b].push_back(Edge(a, b2a, a2b_index));
  25. 	}
  26.  
  27. 	bool assign_levels(int source, int sink) {
  28. 		fill(levels.begin(), levels.end(), -1);
  29. 		queue<int> q; q.push(source);
  30. 		levels[source] = 0;
  31. 		while(!q.empty()) {
  32. 			int here = q.front(); q.pop();
  33. 			for(int i = 0; i < adj[here].size(); ++i) { 
  34. 				const Edge& e = adj[here][i]; 
  35. 				if(levels[e.target] == -1 && e.residual() > 0) {
  36. 					levels[e.target] = levels[here] + 1;
  37. 					q.push(e.target);
  38. 				}
  39. 			}
  40. 		}
  41. 		return levels[sink] != -1;
  42. 	}
  43.  
  44. 	int push_flow(int here, int sink, int flow) {
  45. 		if(here == sink) return flow;
  46.  
  47. 		for(int& i = edges_tried[here]; i < adj[here].size(); ++i) { 
  48. 			Edge& e = adj[here][i]; 
  49. 			if(e.residual() > 0 && levels[e.target] == levels[here]+1) {
  50. 				int amt = push_flow(e.target, sink, min(flow, e.residual()));
  51. 				if(amt > 0) {
  52. 					Edge& e_inv = adj[e.target][e.inverse_index];
  53. 					e.flow += amt;
  54. 					e_inv.flow = -e.flow;
  55. 					return amt;
  56. 				}
  57. 			}
  58. 		}
  59. 		return 0;
  60. 	}
  61.  
  62. 	int go(int source, int sink) {
  63. 		int total_flow = 0;
  64. 		while(assign_levels(source, sink)) {
  65. 			fill(edges_tried.begin(), edges_tried.end(), 0);
  66. 			while(true) {
  67. 				int pushed = push_flow(source, sink, numeric_limits<int>::max());
  68. 				if(pushed == 0) break;
  69. 				total_flow += pushed;
  70. 			}
  71. 		}
  72. 		return total_flow;
  73. 	}
  74. };
  75. int main() {
  76. 	int n, m;
  77. 	scanf("%d%d",&n,&m);
  78. 	NetworkFlow f(n+m+2);
  79. 	int a, b, c, res = 0;
  80. 	for (int i = 1; i <= n; i++) {
  81. 		scanf("%d",&c);
  82. 		f.add_edge(m+i,n+m+1,c,0);
  83. 	}
  84. 	for (int i = 1; i <= m; i++) {
  85. 		scanf("%d%d%d",&a,&b,&c);
  86. 		f.add_edge(i,m+a,inf,0);
  87. 		f.add_edge(i,m+b,inf,0);
  88. 		f.add_edge(0,i,c,0);
  89. 		res += c;
  90. 	}
  91. 	res -= f.go(0, m+n+1);
  92. 	printf("%d",res);
  93. }
Success #stdin #stdout 0s 3440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MiMwkd
language:
C++ (gcc 8.3)
created:
9 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!