Source code for submission s541

Go to diff to previous submission

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. p.clear();
  52. MM(deg, 0);
  53. FOR(i, 0, 1014)
  54. {
  55. nodes[i].clear();
  56. MM(adj[i], 0);
  57. }
  58. FOR(i, 0, n - 1)
  59. {
  60. int from, to, weight;
  61. scanf("%d%d%d", &from, &to, &weight);
  62. nodes[from].PB(to);
  63. adj[from][to] = weight;
  64. ++deg[from];
  65. nodes[to].PB(from);
  66. adj[to][from] = weight;
  67. ++deg[to];
  68. }
  69. s = c;
  70. FOR(i, 1, n + 1) if (deg[i] == 1)
  71. {
  72. nodes[i].PB(1009);
  73. adj[i][1009] = INF;
  74. }
  75. t = 1009;
  76. max_flow = 0;
  77. while (1)
  78. {
  79. f = 0;
  80. queue<int> q; map<int, int> dist;
  81. q.push(s); dist[s] = 0;
  82. while (!q.empty())
  83. {
  84. int u = q.front(); q.pop();
  85. if (u == t) break;
  86. vector<int>::iterator v;
  87. for (v = nodes[u].begin(); v != nodes[u].end(); v++)
  88. {
  89. if (adj[u][*v] > 0 && !dist.count(*v))
  90. {
  91. dist[*v] = dist[u] + 1;
  92. q.push(*v);
  93. p[*v] = u;
  94. }
  95. }
  96. }
  97. augmentPath(t, INF);
  98. if (f == 0) break;
  99. max_flow += f;
  100. }
  101. printf("%d\n", max_flow);
  102. }
  103. return 0;
  104. }
  105.  

Diff to submission s488

fr.cpp

--- c5.s488.cteam011.fr.cpp.0.fr.cpp
+++ c5.s541.cteam011.fr.cpp.0.fr.cpp
@@ -49,4 +49,5 @@
   while (scanf("%d%d", &n, &c) == 2)
   {
+    p.clear();
     MM(deg, 0);
     FOR(i, 0, 1014)