34 lp.addRow(LP::INF,e,23); |
35 lp.addRow(LP::INF,e,23); |
35 lp.addRow(LP::INF,3.0*(p1+p2)-p3,23); |
36 lp.addRow(LP::INF,3.0*(p1+p2)-p3,23); |
36 lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23); |
37 lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23); |
37 lp.addRow(LP::INF,3.0*(p1+p2*2-5*p3+12-p4/3)+2*p4-4,23); |
38 lp.addRow(LP::INF,3.0*(p1+p2*2-5*p3+12-p4/3)+2*p4-4,23); |
38 lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23); |
39 lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23); |
|
40 |
|
41 lp.addRow(x[1]+x[3]<=x[5]-3); |
|
42 lp.addRow(-7<=x[1]+x[3]-12<=3); |
39 } |
43 } |
40 |
44 |
|
45 |
|
46 template<class G,class C> |
|
47 double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t) |
|
48 { |
|
49 LpGlpk lp; |
|
50 |
|
51 typedef G Graph; |
|
52 typedef typename G::Node Node; |
|
53 typedef typename G::NodeIt NodeIt; |
|
54 typedef typename G::Edge Edge; |
|
55 typedef typename G::EdgeIt EdgeIt; |
|
56 typedef typename G::OutEdgeIt OutEdgeIt; |
|
57 typedef typename G::InEdgeIt InEdgeIt; |
|
58 |
|
59 typename G::EdgeMap<LpGlpk::Col> x(g); |
|
60 // lp.addColSet(x); |
|
61 for(EdgeIt e(g);e!=INVALID;++e) x[e]=lp.addCol(); |
|
62 |
|
63 for(EdgeIt e(g);e!=INVALID;++e) { |
|
64 lp.setColUpperBound(x[e],cap[e]); |
|
65 lp.setColLowerBound(x[e],0); |
|
66 } |
|
67 |
|
68 for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) { |
|
69 LpGlpk::Expr ex; |
|
70 for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e]; |
|
71 for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e]; |
|
72 lp.addRow(0,ex,0); |
|
73 } |
|
74 { |
|
75 LpGlpk::Expr ex; |
|
76 for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e]; |
|
77 for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e]; |
|
78 lp.setObj(ex); |
|
79 } |
|
80 |
|
81 lp.solve(); |
|
82 |
|
83 return 0; |
|
84 } |
41 |
85 |
42 int main() |
86 int main() |
43 { |
87 { |
44 LpSolverSkeleton lp_skel; |
88 LpSolverSkeleton lp_skel; |
45 LpGlpk lp_glpk; |
89 LpGlpk lp_glpk; |
46 |
90 |
47 lpTest(lp_skel); |
91 lpTest(lp_skel); |
48 lpTest(lp_glpk); |
92 lpTest(lp_glpk); |
|
93 |
|
94 ListGraph g; |
|
95 ListGraph::EdgeMap<double> cap(g); |
|
96 |
|
97 maxFlow(g,cap,ListGraph::NodeIt(g),ListGraph::NodeIt(g)); |
|
98 |
49 } |
99 } |