mayoko’s diary

プロコンとかいろいろ。

SRM 480 div1 med: NetworkSecurity

解法

まず, クライアント - クライアント間には data-gate をつなげる必要がないことがわかります。
これは, 例えばクライアント i-j 間に data-gate をつなげることによって, i-j-k-...-n -> Server とつながるルートの対策をしたとすると, n とサーバー間にだけ data-gate をつなげれば良いことから言えます。

なので, やるべきこととしては, 各サーバー S について, S につながっている最も下流の辺を入れる, ということだけです。
与えられたグラフは DAG になっているので, これはそんなに難しくなくて, あるクライアント c からあるサーバー s に到達可能である時, c から到達可能な別の任意のクライアント C について, c -> C に到達できてかつ C -> s に到達可能であるなら, c -> s へのルートは下流ではないのでここには data-gate を入れません。そうでない場合は, c -> s は下流なので, data-gate を入れておきます。

bool graph[111][111];

class NetworkSecurity {
public:
    int secureNetwork(vector <string> clientCable, vector <string> serverCable) {
        memset(graph, false, sizeof(graph));
        int N = clientCable.size(), M = serverCable[0].size(), V = N+M;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                graph[i][j] = (clientCable[i][j] == 'Y');
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                graph[i][j+N] = (serverCable[i][j] == 'Y');
            }
        }
        for (int k = 0; k < V; k++) for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) graph[i][j] |= (graph[i][k] & graph[k][j]);
        int ret = 0;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) if (graph[j][i+N]) {
                bool ok = true;
                for (int k = 0; k < N; k++) {
                    if (graph[j][k] && graph[k][i+N]) ok = false;
                }
                if (ok) ret++;
            }
        }
        return ret;
    }
};