Source code for submission s488

fr.cpp

  1. #include <algorithm>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <cstring>
  6. #include <iostream>
  7. #include <sstream>
  8. #include <map>
  9. #include <set>
  10. #include <queue>
  11. #include <vector>
  12.  
  13. using namespace std;
  14.  
  15. #define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++)
  16. #define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--)
  17. #define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--)
  18.  
  19. #define PB push_back
  20. #define MP make_pair
  21.  
  22. #define MM(co, cim) memset((co), (cim), sizeof((co)))
  23.  
  24. #define DEB(x) cerr << ">>> " << #x << " : " << x << endl;
  25.  
  26. #define INF 2000000014
  27.  
  28. map<int, int> p;
  29. int n, c, f, s, t, adj[1014][1014], deg[1014], max_flow;
  30. vector<int> nodes[1014];
  31.  
  32. void augmentPath (int v, int minEdge)
  33. {
  34. if (v == s)
  35. {
  36. f = minEdge;
  37. return;
  38. }
  39. else if (p.count(v))
  40. {
  41. augmentPath(p[v], min(minEdge, adj[p[v]][v]));
  42. adj[p[v]][v] -= f;
  43. adj[v][p[v]] += f;
  44. }
  45. }
  46.  
  47. int main ()
  48. {
  49. while (scanf("%d%d", &n, &c) == 2)
  50. {
  51. MM(deg, 0);
  52. FOR(i, 0, 1014)
  53. {
  54. nodes[i].clear();
  55. MM(adj[i], 0);
  56. }
  57. FOR(i, 0, n - 1)
  58. {
  59. int from, to, weight;
  60. scanf("%d%d%d", &from, &to, &weight);
  61. nodes[from].PB(to);
  62. adj[from][to] = weight;
  63. ++deg[from];
  64. nodes[to].PB(from);
  65. adj[to][from] = weight;
  66. ++deg[to];
  67. }
  68. s = c;
  69. FOR(i, 1, n + 1) if (deg[i] == 1)
  70. {
  71. nodes[i].PB(1009);
  72. adj[i][1009] = INF;
  73. }
  74. t = 1009;
  75. max_flow = 0;
  76. while (1)
  77. {
  78. f = 0;
  79. queue<int> q; map<int, int> dist;
  80. q.push(s); dist[s] = 0;
  81. while (!q.empty())
  82. {
  83. int u = q.front(); q.pop();
  84. if (u == t) break;
  85. vector<int>::iterator v;
  86. for (v = nodes[u].begin(); v != nodes[u].end(); v++)
  87. {
  88. if (adj[u][*v] > 0 && !dist.count(*v))
  89. {
  90. dist[*v] = dist[u] + 1;
  91. q.push(*v);
  92. p[*v] = u;
  93. }
  94. }
  95. }
  96. augmentPath(t, INF);
  97. if (f == 0) break;
  98. max_flow += f;
  99. }
  100. printf("%d\n", max_flow);
  101. }
  102. return 0;
  103. }
  104.