Source code for submission s686

fr.cpp

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <map>
  5. #include <stack>
  6. #include <queue>
  7.  
  8. typedef unsigned int uint;
  9.  
  10. struct Edge;
  11. struct Node;
  12.  
  13. typedef std::vector<Edge *> Edges;
  14. typedef std::vector<Node *> Nodes;
  15.  
  16. struct Edge {
  17. uint visited;
  18. int flow, capacity;
  19. Edge* reverse;
  20. Node* from;
  21. Node* to;
  22.  
  23. Edge(const int capacity, Node& from, Node& to):
  24. visited(0),
  25. flow(0),
  26. capacity(capacity),
  27. reverse(NULL),
  28. from(&from),
  29. to(&to) {
  30. }
  31.  
  32. bool visit(const uint visit) {
  33. if (visited == visit)
  34. return false;
  35.  
  36. visited = visit;
  37. return true;
  38. }
  39.  
  40. int available() const {
  41. return capacity - flow;
  42. }
  43. };
  44.  
  45. struct Node {
  46. uint id;
  47. uint visited;
  48. Node* whence;
  49. Edge* through;
  50. Edges in, out;
  51.  
  52. Node(uint id):
  53. id(id),
  54. visited(0) {
  55. }
  56.  
  57. bool visit(const uint visit) {
  58. if (visited == visit)
  59. return false;
  60.  
  61. visited = visit;
  62. return true;
  63. }
  64. };
  65.  
  66. struct Edge_less_available {
  67. bool operator() (const Edge *const a, const Edge *const b) {
  68. return a->available() < b->available();
  69. }
  70. };
  71.  
  72. bool touches(const Edges& edges, Node& node) {
  73. for (Edges::const_iterator it = edges.begin(); it != edges.end(); it++)
  74. {
  75. Edge& edge = **it;
  76.  
  77. if (&node == edge.from)
  78. return true;
  79. if (&node == edge.to)
  80. return true;
  81. }
  82.  
  83. return false;
  84. }
  85.  
  86. struct Graph {
  87. int flow;
  88. uint visit;
  89. Node* source;
  90. Node* sink;
  91.  
  92. Nodes nodes;
  93. Edges edges;
  94.  
  95. Graph(const uint nNodes, const uint idSource):
  96. flow(0),
  97. visit(0),
  98. source(NULL),
  99. sink(NULL) {
  100.  
  101. for (uint idNode = 0; idNode <= nNodes + 1; idNode++)
  102. nodes.push_back(new Node(idNode));
  103.  
  104. source = nodes[idSource];
  105. sink = nodes[nNodes + 1];
  106. }
  107.  
  108. ~Graph() {
  109. for (Nodes::iterator it = nodes.begin(); it != nodes.end(); it++)
  110. delete *it;
  111. for (Edges::iterator it = edges.begin(); it != edges.end(); it++)
  112. delete *it;
  113. }
  114.  
  115. void add_edge(const uint idFrom, const uint idTo, const int capacity) {
  116. Node& from = *nodes[idFrom];
  117. Node& to = *nodes[idTo ];
  118.  
  119. Edge* edgeFw = new Edge(capacity, from, to);
  120. Edge* edgeBw = new Edge(capacity, to, from);
  121.  
  122. edges.push_back(edgeFw);
  123. edges.push_back(edgeBw);
  124.  
  125. edgeFw->reverse = edgeBw;
  126. edgeBw->reverse = edgeFw;
  127.  
  128. from.out.push_back(edgeFw);
  129. from.in .push_back(edgeBw);
  130. to .in .push_back(edgeFw);
  131. to .out.push_back(edgeBw);
  132. }
  133.  
  134. void dfs(Edges& path) {
  135. visit++;
  136. Node& node = *source;
  137. bool found = dfs_next(path, node);
  138. if (!found)
  139. throw std::exception();
  140. }
  141.  
  142. bool dfs_next(Edges& path, Node& node) {
  143. if (&node == sink)
  144. return true;
  145.  
  146. for (Edges::iterator it = node.out.begin(); it != node.out.end(); it++)
  147. {
  148. Edge& edge = **it;
  149. Node& dest = *edge.to;
  150.  
  151. //~ std::cerr << "considering edge " << node.id << "-" << dest.id << ": " << edge.available() << std::endl;
  152.  
  153. if (touches(path, dest))
  154. continue;
  155. if (!edge.visit(visit) || edge.available() <= 0)
  156. continue;
  157.  
  158. path.push_back(&edge);
  159.  
  160. bool result = dfs_next(path, dest);
  161. if (result)
  162. return true;
  163.  
  164. path.pop_back();
  165. }
  166.  
  167. return false;
  168. }
  169.  
  170. void sinkify() {
  171. visit++;
  172. Node& node = *source;
  173. node.visit(visit);
  174. sinkify_next(node);
  175. }
  176.  
  177. void sinkify_next(Node& node) {
  178. uint outEdges = 0;
  179.  
  180. for (Edges::iterator it = node.out.begin(); it != node.out.end(); it++)
  181. {
  182. Edge& edge = **it;
  183. Node& dest = *edge.to;
  184.  
  185. if (!dest.visit(visit))
  186. continue;
  187.  
  188. outEdges++;
  189. sinkify_next(dest);
  190. }
  191.  
  192. if (outEdges == 0)
  193. add_edge(node.id, sink->id, 1000000);
  194.  
  195. }
  196.  
  197. void maximize() {
  198. while (true)
  199. {
  200. Edges path;
  201.  
  202. try {
  203. dfs(path);
  204.  
  205. //~ std::cerr << "path " << visit << ": " << source->id;
  206. //~ for (Edges::iterator it = path.begin(); it != path.end(); it++)
  207. //~ {
  208. //~ Node* cur = (*it)->to;
  209. //~ std::cerr << " -(" << (*it)->available() << ")- " << cur->id;
  210. //~ }
  211. //~ std::cerr << std::endl;
  212. } catch (std::exception) {
  213. break;
  214. }
  215.  
  216. int flowIncrease;
  217. {
  218. Edge& edge = **std::min_element(path.begin(), path.end(), Edge_less_available());
  219. flowIncrease = edge.available();
  220. }
  221.  
  222. flow += flowIncrease;
  223. for (Edges::iterator it = path.begin(); it != path.end(); it++)
  224. {
  225. Edge& edge = **it;
  226. Edge& reverse = *edge.reverse;
  227.  
  228. edge.flow += flowIncrease;
  229. reverse.flow -= flowIncrease;
  230. }
  231. }
  232. }
  233. };
  234.  
  235. int main() {
  236. while (true)
  237. {
  238. uint nNodes, idSource;
  239. std::cin >> nNodes >> idSource;
  240. if (std::cin.fail())
  241. break;
  242.  
  243. Graph sprink(nNodes, idSource);
  244.  
  245. for (uint i = 0; i < nNodes - 1; i++)
  246. {
  247. uint idFrom, idTo;
  248. int capacity;
  249.  
  250. std::cin >> idFrom >> idTo >> capacity;
  251. sprink.add_edge(idFrom, idTo, capacity);
  252. }
  253.  
  254. sprink.sinkify();
  255.  
  256. //~ for (Edges::iterator it = sprink.edges.begin(); it != sprink.edges.end(); it++)
  257. //~ std::cerr << "edge " << (*it)->from->id << " - " << (*it)->to->id << ": " << (*it)->capacity << std::endl;
  258.  
  259. sprink.maximize();
  260.  
  261. std::cout << sprink.flow << std::endl;
  262. }
  263.  
  264. return 0;
  265. }
  266.