26 preflow_push<ListGraph, int> max_flow_test(G, s, t, cap); |
26 preflow_push<ListGraph, int> max_flow_test(G, s, t, cap); |
27 int flow_value=max_flow_test.run(); |
27 int flow_value=max_flow_test.run(); |
28 //ListGraph::NodeMap<bool> cut=max_flow_test.mincut(); |
28 //ListGraph::NodeMap<bool> cut=max_flow_test.mincut(); |
29 //int cut_value=0; |
29 //int cut_value=0; |
30 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { |
30 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { |
31 // if (cut.get(G.tail(e)) && !cut.get(G.head(e))) cut_value+=cap.get(e); |
31 // if (cut.get(G.source(e)) && !cut.get(G.target(e))) cut_value+=cap.get(e); |
32 //} |
32 //} |
33 double post_time=currTime(); |
33 double post_time=currTime(); |
34 //std::cout << "maximum flow: "<< std::endl; |
34 //std::cout << "maximum flow: "<< std::endl; |
35 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { |
35 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { |
36 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
36 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; |
37 //} |
37 //} |
38 //std::cout<<std::endl; |
38 //std::cout<<std::endl; |
39 std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl; |
39 std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl; |
40 std::cout << "flow value: "<< flow_value << std::endl; |
40 std::cout << "flow value: "<< flow_value << std::endl; |
41 //std::cout << "cut value: "<< cut_value << std::endl; |
41 //std::cout << "cut value: "<< cut_value << std::endl; |