SRM480 Midium:NetworkSecurity

keyword

有向グラフ　C++

概要

有向非巡回グラフをなすクライアント群とクライアントと繋がっているサーバ群が与えられる。クライアントCからサーバSへの経路が存在するとき少なくとも一つの経路上にゲートがあるようにしたい。ゲートを置く最小個数を求める問題。
450点問題だったのでグラフでも諦めずに読み込む。最初は最大流かと思ったけどもっと単純で、各サーバを基準に考えて繋がっているクライアントの中で極大なものだけをカウントすればよさそう。証明はしてないけどサンプルが通ったので投げた。結果は無事AC。

int secureNetwork(vector <string> clientCable, vector <string> serverCable) {
    int i, j, k,c=SZ(clientCable), s=SZ(serverCable[0]);
    vector< vector<int> > canGo(c);
    REP(i,c){
        set<int> cur, next;
        vector<bool> visited(c,false);
        REP(j,c)if(clientCable[i][j]=='Y') cur.insert(j);
        visited[i] = true;
        while(!cur.empty()){
            EACH(cur,it)canGo[i].PB(*it);
            next.clear();
            EACH(cur,it){
                REP(k,c){
                    if(!visited[k] && clientCable[*it][k] == 'Y'){
                        visited[k] = true;
                        next.insert(k);
                    }
                }
            }
            cur = next;
        }
    }

    vector< vector<int> > froms(s);
    REP(i,s){
        REP(j,c)if(serverCable[j][i]=='Y'){
            REP(k,SZ(canGo[j])){
                if(serverCable[canGo[j][k]][i]=='Y')
                    break;
            }
            if(k==SZ(canGo[j])){
                froms[i].PB(j);
            }
        }
    }

    int ret = 0;
    REP(i,s){
        ret += SZ(froms[i]);
    }

    return ret;
}