yukicoder No.119 旅行のツアーの問題

解法

燃やす埋める問題と呼ばれるものです。最大流(最小カット)を使います。
・$x$番目の国に行かない
・$x$番目の国に行くけど、ツアーに行かない
・$x$番目の国に行き、ツアーにも行く
という3択があります。まず、 M 個の条件がない場合は、以下のように頂点を倍加して、辺を張ることでこの3択を実現できます。
ここでは、$s$を始点、$t$を終点とします。

今回は、
①ツアーに行く満足度$A$
②ツアーに行く満足度+ツアーに行かないけど国に行く満足度$A+B$
③ツアーに行かないけど国に行く$B$
という順番で上流から辺を張りました。順番は任意で構いませんが、M個の条件を追加する際に真ん中が$A+B$の容量の辺だと都合が良いと思います。答えは$A+B$を持っていて、そこから流量の分だけ損失があると考えます。
それぞれがカットされた場合を考えます。

①$A$がカットされた(すなわち流量$A$が流れた)
$A$がカットされた(すなわち流量$A$が流れた)場合は、答えは$A+B-A=B$になります。すなわち、国に行くけどツアーに行かないのが最適ということになります。

②$A+B$がカットされた(すなわち流量$A+B$が流れた)
$A+B$がカットされた(すなわち流量$A+B$が流れた)場合は、答えは$A+B-(A+B)=0$になります。すなわち、国に行かないことが最適となります。(M個の条件がない場合ではこの選択肢は取り得ないことが分かるかと思います。)

③$B$がカットされた(すなわち流量$B$が流れた)
$B$がカットされた(すなわち流量$B$が流れた)場合は、答えは$A+B-B=A$になります。すなわち、国に行きツアーにも参加することが最適となります。

言い換えると、それぞれの辺をカットすることは以下の選択肢を選んだことに相当することが分かるかと思います。 ①国に行くけどツアーに行かない
②国に行かない
③国に行きツアーにも行く

そして、M個の条件を考えます。$u$<$v$の条件が成り立っており、$u$、$v$両方の国を訪れる場合、$u$の国でツアーを利用したら$v$の国でもツアーを利用しなければならないことにします。
結論から言ってしまうと、以下のように$u'$から$v$に容量が十分に大きいINFの辺を張ることで達成できます。仮に、国$u$に行きツアーにも行く選択をした後、国$v$に行くけどツアーに行かない選択をした場合、容量が$B_u$と$A_v$の辺がカットされますが、$s \to u\to u' \to v \to v' \to t$の経路でまだ流量を流すことができますので、最適でないことが分かります。これはすなわち、国$u$で③の選択肢を取ったならば、国$v$では②か③の選択肢を選ばなければいけないといったような状況に相当します。今回は、国$u$で③の選択肢を取ったならば条件先の国$v$では②か③の2択になるといった具合でしたが、$u'\to v'$などに容量INFの辺を張ると③を選んだら条件先では③の一択になるなどといった応用もできます。容量INFの辺の始点よりも下流にある辺をカットする場合は、容量INFの辺の終点よりも下流の辺をカットしなければならないということが一般的に言えます。
逆に、国$v$で①の選択肢を取ったらならば、国$u$では①か②の2択になるといった見方もできます。容量INFの辺の終点よりも上流にある辺をカットする場合は、容量INFの辺の始点よりも上流の辺をカットしなければならないということが一般的に言えます。辺の向きと始点と終点を逆にしたものも流量が同じになることが分かるかと思いますが、これも国$u$でINFの辺の終点より上流の選択肢(③)を選んだならば、国$v$ではINFの辺の始点よりも上流の選択肢(②か③)を選ばなければいけないと解釈することができます。(最初に、①、②、③の辺の順序は②が真ん中ならば任意で良いと書かせて頂いたのもこのためです。)

まとめると、
・INFの辺の始点よりも下流の辺をカットしたならば、INFの辺の終点よりも下流の辺をカットしなければならない
・INFの辺の終点よりも上流の辺をカットしたならば、INFの辺の始点よりも上流の辺をカットしなければならない
といったことを考えることで、M個の条件を追加することができました。
これらが同じことを指しているのは以下の2つが対偶関係となっているためです。
・INFの辺の始点よりも下流の辺をカットするならば、INFの辺の終点よりも下流の辺をカットする
・INFの辺の終点よりも下流の辺をカットしないならば、INFの辺の始点よりも下流の辺をカットしない

今回の問題で言うと、以下の2つが対偶関係にあることが分かるかと思います。
・国$u$でツアーに行ったならば、国$v$に行くときはツアーに行く
・国$v$に行くときにツアーに行かなかったならば、国$u$でツアーに行ってはいけない

実装例

実装にはAtCoder Libraryのmax_flowを用いています。

#include<atcoder/all>
using namespace std;

int main(){
    int n, m, u, v;
    cin >> n;
    atcoder::mf_graph<int> g(2 * n + 2);
    int s = 2 * n, t = s + 1, ans = 0;
    for(int i = 0; i < n; i++){
        cin >> u >> v;
        ans += u + v;
        g.add_edge(s, i, u);
        g.add_edge(i, i + n, u + v);
        g.add_edge(i + n, t, v);
    }
    cin >> m;
    for(int i = 0; i < m; i++){
        cin >> u >> v;
        g.add_edge(u + n, v, 1 << 30);
    }
    ans -= g.flow(s, t);
    cout << ans << endl;
}