備忘録

まとめておきたいことのメモ 主にプロコンのこと

ABC 010 D

今回はこの問題を解きました。

abc010.contest.atcoder.jp

あるSNSにおいて、0からn-1のn人の友人関係が与えられます。このSNSにおいては直接友達ではない人でも、自分の友達を介することでその人からのメッセージをみることができます。このうち、指定されたp人から送られるメッセージを0番の人が見られないようにしたいです。そのために以下の操作をすきなだけ行うことができます。
1. ある二人組の友人関係を解消する。
2. ある人がログインできないようにする。
できるだけ操作回数をすくなくしたとき、その操作回数はいくつになるでしょうか、という問題です。

わからなかったので解説を見ました。
最大フロー最小カットの定理を使うそうです。内容とか証明はググったらたくさん出てきます。去年グラフ理論で学びましたがすっかり忘れていました。
改めて考えておもしろい定理だなあと思いました。
この問題では枝は両方向であること、枝の重みはすべて1であることに注意して最大流問題をとけばオッケーです。
解答は以下のようになりました。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define pai 3.14159265359
    #define mod 1000000007
     
    vector<int> getpath(int n, int r[101][101])
    {
        // for(int i = 0; i <= n; i++){
        //     for(int j = 0; j <= n; j++){
        //         cout << r[i][j];
        //     }
        //     cout << endl;
        // }
        stack<int> st;
        vector<int> result;
        vector<int> beforenode(n + 1, -1);
        st.push(0);
        while(!st.empty()){
            int nownode = st.top();
            // cout << nownode << endl;
            st.pop();
            if(nownode == n){
                result.push_back(n);
                int parent = beforenode[n];
                while(parent != -1){
                    result.push_back(parent);
                    parent = beforenode[parent];
                }
                reverse(result.begin(), result.end());
                return result;
            }
            for(int i = 1; i <= n; i++){
                if(r[nownode][i] == 1 && beforenode[i] == -1){
                    beforenode[i] = nownode;
                    st.push(i);
                }
            }
        }
        return result;
    }
     
    int main()
    {
        int n, g, e;
        cin >> n >> g >> e;
        int p[101];
        for(int i = 0; i < g; i++){
            cin >> p[i];
        }
        int capacity[101][101] = {};
        int flow[101][101] = {};
        int residual[101][101] = {};
        for(int i = 0; i < e; i++){
            int a, b;
            cin >> a >> b;
            capacity[a][b] = 1;
            capacity[b][a] = 1;
            residual[a][b] = 1;
            residual[b][a] = 1;
        }
        for(int i = 0; i < g; i++){
            capacity[p[i]][n] = 1;
            capacity[n][p[i]] = 1;
            residual[p[i]][n] = 1;
            residual[n][p[i]] = 1;
        }
        vector<int> augumeting_path = getpath(n, residual);
        while(augumeting_path.size() != 0){
            // cout << augumeting_path.size() << endl;
            // cout << endl;
            for(int i = 0; i < augumeting_path.size() - 1; i++){
                int node = augumeting_path[i];
                // cout << node << " ";
                int nextnode = augumeting_path[i + 1];
                // cout << nextnode << endl;
                flow[node][nextnode]++;
                residual[node][nextnode]--;
                residual[nextnode][node]++;
            }
            augumeting_path = getpath(n, residual);
        }
        int ans = 0;
        for(int i = 0; i < n; i++){
            ans += flow[i][n];
        }
        cout << ans << endl;  
    }

capacity、residual、flowはそれぞれそのままその枝の容量、残余ネットワークでの値、フローの値を表しています。最初フローはすべて0で、道がある部分については残余ネットワークでの値が1になっています。
getpath関数では増加道を深さ優先探索で調べています。増加道が存在しない場合はからのベクタを返します。
増加道が見つかれば、それに沿ってflowとresidualの値を更新します。これを増加道が見つからなくなるまで繰り返します。最後にノードnに流れてくる総量を求めて答えを出します。

重みは1しかないのだからcapacityは使ってません。ガバガバですね。
今度は重みつきグラフでの問題に挑戦してみたいです。