OI-Wiki 中给出了最小割的一种经典模型,用割边表示两点在不同集合的代价,对于限制条件 u,v,wu,v,wu,v,w,我们在 u,vu,vu,v 之间连容量为 www 的双向边。
双向边
Q1:请问双向边如何建立?
Q2:请问建立 u->v 和 v->u 的单向边为何正确?不会导致 w 被计算两次吗?
u->v
v->u
w
注:单向边是这样建立的。
E.push_back({to, cap}); E.push_back({from, 0});