Advertisement
Guest User

Untitled

a guest
Sep 30th, 2015
232
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.34 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <sstream>
  4. #include <utility>
  5. #include <cstdlib>
  6. #include <cstring>
  7. #include <cassert>
  8. #include <fstream>
  9. #include <cstdio>
  10. #include <string>
  11. #include <vector>
  12. #include <queue>
  13. #include <cmath>
  14. #include <ctime>
  15. #include <stack>
  16. #include <map>
  17. #include <set>
  18.  
  19. using namespace std;
  20.  
  21. #define pb push_back
  22. #define ppb pop_back
  23. #define mp make_pair
  24. #define N 50
  25. #define f first
  26. #define s second
  27. #define abs(a) ((a) < 0 ? -(a) : (a))
  28. #define sqr(a) ((a) * (a))
  29.  
  30. typedef unsigned int uint;
  31. typedef long long ll;
  32. typedef unsigned long long ull;
  33.  
  34. const double eps = 1e-9;
  35. const int mod = (int)1e+9 + 7;
  36. const double pi = acos(-1.);
  37. const int maxn = 5000;
  38.  
  39. #define inf (1ll << 30)
  40. char ch;
  41.  
  42. ll x, y, z, n, m;
  43. double d[maxn];
  44.  
  45. int s, t;
  46. bool was[maxn];
  47. pair <int, pair <int, int> > p[maxn];
  48. pair <int, int> a[maxn], b[maxn];
  49.  
  50. double pot[1000];
  51.  
  52. int q[int(1e6)];
  53.  
  54. bool inqueue[int(1e6)];
  55.  
  56. struct Edge{
  57. int to, cap, flow;
  58. double cost;
  59. int id;
  60. };
  61. vector <Edge> g[maxn];
  62.  
  63. set < pair < double, int > > qe;
  64.  
  65.  
  66. bool djikstra(int s, int t) {
  67. for (int i = 0; i <= t + 10; i++) {
  68. d[i] = inf;
  69. was[i] = 0;
  70. }
  71. d[s] = 0;
  72. qe.clear();
  73. qe.insert(mp(d[s], s));
  74.  
  75. while (!qe.empty()) {
  76. int v = qe.begin()-> second;
  77. qe.erase(qe.begin());
  78. for (int j = 0; j < g[v].size(); j++) {
  79. int to = g[v][j].to;
  80. double cost = g[v][j].cost;
  81. int cap = g[v][j].cap;
  82. int fl = g[v][j].flow;
  83. if (cap - fl > 0 && d[to] > d[v] + cost + pot[v] - pot[to]) {
  84. qe.erase(mp(d[to], to));
  85. d[to] = d[v] + cost + pot[v] - pot[to];
  86. qe.insert(mp(d[to], to));
  87. p[to] = mp(v, mp(cap-fl, j));
  88. }
  89. }
  90. }
  91. for (int i = 0; i <= t; i++)
  92. if (d[i] != inf)
  93. pot[i] += d[i];
  94. return d[t] != inf;
  95. }
  96.  
  97. double res = 0;
  98.  
  99.  
  100. double getans(int x) {
  101. if (x == 0) return 0;
  102. if (x < 0) {
  103. return (sqrt(-x));
  104. }
  105. return sqrt(x);
  106. }
  107.  
  108. void add(int v, int t, int cap, int fl, double cost) {
  109. Edge e1;
  110. e1.to = t;
  111. e1.cap = cap;
  112. e1.flow = fl;
  113. e1.cost = cost;
  114. e1.id = g[t].size();
  115.  
  116.  
  117. Edge e2;
  118. e2.to = v;
  119. e2.cap = 0;
  120. e2.id = g[v].size();
  121. e2.flow = 0;
  122. e2.cost = -cost;
  123.  
  124. g[v].pb(e1);
  125. g[t].pb(e2);
  126. }
  127.  
  128. double flow(int s, int t) {
  129. int v = t;
  130. int fl = int(1e9);
  131. while (v != s) {
  132. fl = min(fl, p[v].s.f);
  133. v = p[v].f;
  134. }
  135. v = t;
  136. while (v != s) {
  137. g[p[v].f][p[v].s.s].flow += fl;
  138. g[v][g[p[v].f][p[v].s.s].id].flow -= fl;
  139. res += fl * g[p[v].f][p[v].s.s].cost;
  140. v = p[v].f;
  141. }
  142. return 0;
  143. }
  144.  
  145. double dist(int xa, int ya, int xb, int yb) {
  146. return sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
  147. }
  148.  
  149.  
  150. int get(int xa, int ya, int xb, int yb) {
  151. return (xa - xb) * (xa - xb) + (ya - yb) * (ya - yb);
  152. }
  153.  
  154. int main() {
  155. scanf("%d%d%d", &n, &x, &y);
  156.  
  157. for (int i = 1; i <= n; i++) {
  158. scanf("%d%d%d%d", &a[i].f, &b[i].f, &a[i].s, &b[i].s);
  159. //cin >> a[i].f >> b[i].f >> a[i].s >> b[i].s;
  160.  
  161. res += dist(a[i].f, b[i].f, a[i].s, b[i].s);
  162. }
  163. s = 0, t = n + n + 1;
  164.  
  165. for (int i = 1; i <= n; i++)
  166. for (int j = 1; j <= n; j++)
  167. add(i, n + j, 1, 0, dist(a[i].s, b[i].s, a[j].f, b[j].f));
  168.  
  169. for (int i = 1; i <= n; i++)
  170. add(0, i, 1, 0, 0);
  171. for (int i = 1; i <= n; i++)
  172. add(n + i, t, 1, 0, 0);
  173. while (djikstra(s, t)) {
  174. flow(s, n + n + 1);
  175. }
  176.  
  177. printf("%.10lf", res);
  178. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement