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