fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <memory.h>
  4. #include <limits>
  5. #include <algorithm>
  6. #include <functional>
  7. #include <queue>
  8. using namespace std;
  9. namespace MCMF {
  10. 	typedef int cap_t;
  11. 	typedef double cost_t;
  12. 	bool isZeroCap(cap_t cap) {
  13. 		return cap == 0;
  14. 	}
  15. 	const cap_t CAP_MAX = numeric_limits<cap_t>::max();
  16. 	const cost_t COST_MAX = numeric_limits<cost_t>::max();
  17. 	struct edge_t {
  18. 		int target;
  19. 		cap_t cap;
  20. 		cost_t cost;
  21. 		int rev;
  22. 	};
  23. 	int n;
  24. 	vector<vector<edge_t>> graph;
  25. 	vector<cost_t> pi;
  26. 	vector<cost_t> dist;
  27. 	vector<cap_t> mincap;
  28. 	vector<int> from, v;
  29. 	void init(int _n) {
  30. 		n = _n;
  31. 		graph.clear(); graph.resize(n);
  32. 		pi.clear(); pi.resize(n);
  33. 		dist.resize(n);
  34. 		mincap.resize(n);
  35. 		from.resize(n);
  36. 		v.resize(n);
  37. 	}
  38. 	void addEdge(int a, int b, cap_t cap, cost_t cost) {
  39. 		edge_t forward = { b, cap, cost, (int)graph[b].size() };
  40. 		edge_t backward = { a, 0, -cost, (int)graph[a].size() };
  41. 		graph[a].push_back(forward);
  42. 		graph[b].push_back(backward);
  43. 	}
  44. 	bool dijkstra(int s, int t) {
  45. 		typedef pair<cost_t, int> pq_t;
  46. 		priority_queue<pq_t, vector<pq_t>, greater<pq_t>> pq;
  47. 		fill(dist.begin(), dist.end(), COST_MAX);
  48. 		memset(&from[0], -1, n*sizeof(from[0]));
  49. 		memset(&v[0], 0, n*sizeof(v[0]));
  50. 		dist[s] = 0;
  51. 		mincap[s] = CAP_MAX;
  52. 		pq.emplace(make_pair(dist[s], s));
  53. 		while (!pq.empty()) {
  54. 			int cur = pq.top().second; pq.pop();
  55. 			if (v[cur]) continue;
  56. 			v[cur] = 1;
  57. 			if (cur == t) continue;
  58. 			for (int k = 0; k < graph[cur].size(); k++) {
  59. 				edge_t edge = graph[cur][k];
  60. 				int next = edge.target;
  61. 				if (v[next]) continue;
  62. 				if (isZeroCap(edge.cap)) continue;
  63. 				cost_t potCost = dist[cur] + edge.cost - pi[next] + pi[cur];
  64. 				if (dist[next] <= potCost) continue;
  65. 				dist[next] = potCost;
  66. 				mincap[next] = min(mincap[cur], edge.cap);
  67. 				from[next] = edge.rev;
  68. 				pq.emplace(make_pair(dist[next], next));
  69. 			}
  70. 		}
  71. 		if (dist[t] == COST_MAX) return false;
  72. 		for (int i = 0; i < n; i++) {
  73. 			if (dist[i] == COST_MAX) continue;
  74. 			pi[i] += dist[i];
  75. 		}
  76. 		return true;
  77. 	}
  78. 	pair<cap_t, cost_t> solve(int source, int sink) {
  79. 		cap_t total_flow = 0;
  80. 		cost_t total_cost = 0;
  81. 		while (dijkstra(source, sink)) {
  82. 			cap_t f = mincap[sink];
  83. 			total_flow += f;
  84. 			for (int p = sink; p != source;) {
  85. 				auto &backward = graph[p][from[p]];
  86. 				auto &forward = graph[backward.target][backward.rev];
  87. 				forward.cap -= f;
  88. 				backward.cap += f;
  89. 				total_cost += forward.cost * f;
  90. 				p = backward.target;
  91. 			}
  92. 		}
  93. 		return make_pair(total_flow, total_cost);
  94. 	}
  95. }
  96. int x[105], y[105];
  97. int main() {
  98. 	int runs;
  99. 	for (scanf("%d", &runs); runs--;) {
  100. 		int n, m = 0;
  101. 		scanf("%d", &n);
  102. 		MCMF::init(2 * n + 2);
  103. 		int sink = 2 * n + 1;
  104. 		for (int i = 1; i <= n; i++) {
  105. 			scanf("%d%d", &x[i], &y[i]);
  106. 			if (x[i] == 0) { n--; i--; }
  107. 		}
  108. 		for (int i = 1; i <= n; i++) {
  109. 			x[i] = -x[i];
  110. 			int a = i;
  111. 			MCMF::addEdge(0, a, 1, 0);
  112. 			MCMF::addEdge(a, n + a, 1, 2.0*abs(double(x[i])));
  113. 			for (int j = 1; j <= n; j++) {
  114. 				if (i != j && x[j] * x[i] > 0) {
  115. 					int b = n + j;
  116. 					MCMF::addEdge(a, b, 1, sqrt(double((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]))));
  117. 				}
  118. 			}
  119. 			x[i] = -x[i];
  120. 			MCMF::addEdge(n + i, sink, 1, 0);
  121. 		}
  122. 		printf("%.3lf\n", MCMF::solve(0, sink).second / 2.0);
  123. 	}
  124. }
Success #stdin #stdout 0s 3440KB
comments (?)
stdin
copy 
3
1
-2 3
2
2 2
-2 1
8
2 2
7 1
9 -4
-10 1
-6 -9
-6 10
8 8
2 -4
stdout
copy 
2.000
1.000
15.659
https://ideone.com/7fIRdJ
language:
C++14 (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!