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; } };