Source code for submission s712

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

Diff to submission s541

fr.cpp

--- c5.s541.cteam011.fr.cpp.0.fr.cpp
+++ c5.s712.cteam011.fr.cpp.0.fr.cpp
@@ -24,5 +24,5 @@
 #define DEB(x) cerr << ">>> " << #x << " : " << x << endl;
 
-#define INF 2000000014
+#define INF 1000000014
 
 map<int, int> p;
@@ -60,13 +60,22 @@
       int from, to, weight;
       scanf("%d%d%d", &from, &to, &weight);
+      if (to == c)
+      {
+        int tmp = from;
+        from = to;      
+        to = tmp;
+      }
       nodes[from].PB(to);
       adj[from][to] = weight;
       ++deg[from];
-      nodes[to].PB(from);
-      adj[to][from] = weight;
-      ++deg[to];
+      if (from != c)
+      {
+        nodes[to].PB(from);
+        adj[to][from] = weight;
+        ++deg[to];
+      }
     }
     s = c;
-    FOR(i, 1, n + 1) if (deg[i] == 1)
+    FOR(i, 1, n + 1) if (deg[i] <= 1)
     {
       nodes[i].PB(1009);