D - 浮気予防

問題

atcoder.jp

考えていたこと

・を問題文中での悪い虫の頂点集合、を高橋くんとする。
・を含む部分グラフとを含む部分グラフに分ける最小カットを考えればいいことがわかる。
・の要素をすべてに置き換えて最大流を流す　→　”ログインできなくなる”という操作が再現できない。(具体的には、sample3が3になる)

正解

・やっぱり最小カット。とをつなぐを仮定して最大流を流せば良い。
・よく考えると、”ログインできなくさせる”という操作はにだけ行えば良い。
・からへのをカットすると、をログインさせなくなるという操作が実現できる。
・問題をよく読むと頂点を削除することができないですねこれ…ずっとできるものだと思ってた。

解答

最小カット久々に使いました。

#include<bits/stdc++.h>
using ll  = long long;
using namespace std;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
struct Edge{int to,cap,rev;};
class Dinic{//max flow
public:
    int n;
    vector<vector<Edge> >G;
    vector<int> level,iter;
    Dinic(int size): n(size),G(vector<vector<Edge>>(n)){};
    void add_Edge(int from, int to, int cap){
        Edge q={to,cap,int(G[to].size())};
        G[from].emplace_back(q);
        q={from,0,int(G[from].size()-1)};
        G[to].emplace_back(q);
    }
    void bfs(int s){
        level=vector<int>(n,-1);
        queue<int>q;
        level[s]=0;
        q.push(s);
        while(!q.empty()){
            int v=q.front();q.pop();
            for(auto &e :G[v]){
                if(e.cap>0&&level[e.to]<0){
                    level[e.to]=level[v]+1;
                    q.push(e.to);
                }
            }
        }
    }
    function<int(int,int,int)>dfs = [&](int v, int t, int f) -> int{
        if(v==t)return f;
        for(;iter[v]<G[v].size();iter[v]++){
            Edge &e=G[v][iter[v]];
            if(level[v]>=level[e.to]||e.cap<=0) continue;
            int d =dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
        return 0;
    };
    int max_flow(int s,int t) {//from s to t,ford_fulkerson
        int flow=0;
        while(1){
            bfs(s);
            if(level[t]<0)return flow;
            iter=vector<int>(n);
            int f;
            while((f=dfs(s,t,INF))>0)flow+=f;
        }
    };
};
signed main(){
    int N,G,E;
    cin >> N >> G >> E;
    vector<int>p(G);
    for(auto & g : p) cin >> g;
    auto fl = Dinic(N+1);
    int sink = N;
    rep(_,E){
        int a,b; cin >> a >> b;
        fl.add_Edge(a,b,1);
        fl.add_Edge(b,a,1);
    }
    for(auto e : p)fl.add_Edge(e, sink,1);
    cout << fl.max_flow(0,sink) << endl;
}