21 typedef Graph::EachNodeIt EachNodeIt; |
21 typedef Graph::EachNodeIt EachNodeIt; |
22 typedef Graph::EachEdgeIt EachEdgeIt; |
22 typedef Graph::EachEdgeIt EachEdgeIt; |
23 |
23 |
24 Graph G; |
24 Graph G; |
25 NodeIt s, t; |
25 NodeIt s, t; |
|
26 Timer ts; |
26 Graph::DynEdgeMap<int> cap(G); |
27 Graph::DynEdgeMap<int> cap(G); |
27 readDimacsMaxFlow(std::cin, G, s, t, cap); |
28 readDimacsMaxFlow(std::cin, G, s, t, cap); |
28 |
29 |
|
30 std::cout << "loading time: " << ts << std::endl; |
|
31 ts.reset(); |
29 std::cout << "edmonds karp demo..." << std::endl; |
32 std::cout << "edmonds karp demo..." << std::endl; |
30 Graph::DynEdgeMap<int> flow(G); //0 flow |
33 Graph::DynEdgeMap<int> flow(G); //0 flow |
31 |
34 |
32 int ret; |
35 int ret; |
33 double pre_time=currTime(); |
36 // double pre_time=currTime(); |
34 Timer ts; |
|
35 |
37 |
36 ret = maxFlow(G,flow,cap,s,t); |
38 ret = maxFlow(G,flow,cap,s,t); |
37 double post_time=currTime(); |
39 // double post_time=currTime(); |
38 std::cout << "ellapsed time:" << ts << std::endl; |
40 std::cout << "running time: " << ts << std::endl; |
39 |
41 |
40 //std::cout << "maximum flow: "<< std::endl; |
42 //std::cout << "maximum flow: "<< std::endl; |
41 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { |
43 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { |
42 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
44 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
43 //} |
45 //} |
44 //std::cout<<std::endl; |
46 //std::cout<<std::endl; |
45 std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl; |
47 // std::cout<<"elapsed time: " << post_time-pre_time << " sec"<< std::endl; |
46 std::cout << "flow value: "<< ret << std::endl; |
48 std::cout << "flow value: "<< ret << std::endl; |
47 |
49 |
48 return 0; |
50 return 0; |
49 } |
51 } |