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

うまくグラフを作って最小カットにもってく問題。
最小カットをつかっての最小コストでの二値分類ができるのは知っていたけど、この問題の場合は三値分類になってしまうのでどうしたものかと思っていた。
二値分類のときはツアー参加側と未参加側のノードを inf でつなぐのだけど、この問題の場合はその辺を B+C の容量にしてしまえばよい。そうするとその辺を切断するとことが国に訪れない第三の選択となる。勉強になるなー。

class TravelTourProblem {
public:
    // 全ての国に訪れるケースを考えると各国に対してツアーに参加するかどうかの二値分類問題になる。
    // よってその場合は最小カットで解ける。(全流量からカットした分 B or C を取り除く。)
    //
    // 問題は国に訪れないケースも考える必要がある場合。
    // この場合は両方の総和 B+C を取り除くと考える。
    //
    void solve(void) {
            int N,M;
            cin>>N;

            int V = 2*N+2;
            int src = V-2;      // ツアー未参加側
            int sink = src+1;   // ツアー参加側
            int total = 0;
            MF<int> mf(V);
            const auto inf = (1<<30);
            REP(i,N)
            {
                int B,C;
                cin>>B>>C;
                total += (B+C);
                mf.add(src, i, C);
                mf.add(i+N, sink, B);
                mf.add(i,i+N,B+C); // 国に訪れないケースはここを切断すればよい。
            }
            cin>>M;
            REP(i,M)
            {
                int D,E;
                cin>>D>>E;
                //
                //     +-> E1->E2 -/-+
                //     |       v     |
                // src-+   +---+     +-> sink
                //     |   v         |
                //     +-> D1->D2 ---+
                //
                // E 番目のツアー参加への辺を切断しても D->sink が残っているなら
                // flow cut できないようにする。
                //
                mf.add(E+N,D,inf);
            }
            total -= mf.max_flow(src,sink,inf);
            cout<<total<<endl;
    }
};