17 typedef Graph::NodeIt NodeIt; |
17 typedef Graph::NodeIt NodeIt; |
18 typedef Graph::Edge Edge; |
18 typedef Graph::Edge Edge; |
19 typedef Graph::EdgeIt EdgeIt; |
19 typedef Graph::EdgeIt EdgeIt; |
20 typedef Graph::OutEdgeIt OutEdgeIt; |
20 typedef Graph::OutEdgeIt OutEdgeIt; |
21 |
21 |
22 Graph G; |
22 Graph g; |
23 Node s, t; |
23 Node s, t; |
24 Graph::EdgeMap<int> cap(G); |
24 Graph::EdgeMap<int> cap(g); |
25 readDimacsMaxFlow(std::cin, G, s, t, cap); |
25 //readDimacsMaxFlow(std::cin, g, s, t, cap); |
26 Graph::NodeMap<OutEdgeIt> pred(G); |
26 readDimacs(std::cin, g); |
|
27 |
|
28 Graph::NodeMap<OutEdgeIt> pred(g); |
27 Timer ts; |
29 Timer ts; |
28 { |
30 { |
29 ts.reset(); |
31 ts.reset(); |
30 Graph::NodeMap<bool> reached(G); |
32 Graph::NodeMap<bool> reached(g); |
31 reached.set(s, true); |
33 reached.set(s, true); |
32 pred.set(s, INVALID); |
34 pred.set(s, INVALID); |
33 std::queue<Node> bfs_queue; |
35 std::queue<Node> bfs_queue; |
34 bfs_queue.push(t); |
36 bfs_queue.push(t); |
35 while (!bfs_queue.empty()) { |
37 while (!bfs_queue.empty()) { |
36 Node v=bfs_queue.front(); |
38 Node v=bfs_queue.front(); |
37 bfs_queue.pop(); |
39 bfs_queue.pop(); |
38 OutEdgeIt e; |
40 OutEdgeIt e; |
39 for(G.first(e,v); G.valid(e); G.next(e)) { |
41 for(g.first(e,v); g.valid(e); g.next(e)) { |
40 Node w=G.head(e); |
42 Node w=g.head(e); |
41 if (!reached[w]) { |
43 if (!reached[w]) { |
42 bfs_queue.push(w); |
44 bfs_queue.push(w); |
43 reached.set(w, true); |
45 reached.set(w, true); |
44 pred.set(w, e); |
46 pred.set(w, e); |
45 } |
47 } |
49 std::cout << ts << std::endl; |
51 std::cout << ts << std::endl; |
50 } |
52 } |
51 |
53 |
52 { |
54 { |
53 ts.reset(); |
55 ts.reset(); |
54 BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G); |
56 BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g); |
55 bfs.pushAndSetReached(s); |
57 bfs.pushAndSetReached(s); |
56 pred.set(s, INVALID); |
58 pred.set(s, INVALID); |
57 while (!bfs.finished()) { |
59 while (!bfs.finished()) { |
58 ++bfs; |
60 ++bfs; |
59 if (G.valid(bfs) && bfs.isBNodeNewlyReached()) |
61 if (g.valid(bfs) && bfs.isBNodeNewlyReached()) |
60 pred.set(bfs.bNode(), bfs); |
62 pred.set(bfs.bNode(), bfs); |
61 } |
63 } |
62 std::cout << ts << std::endl; |
64 std::cout << ts << std::endl; |
63 } |
65 } |
64 |
66 |