SRM480 Div1 Medium(450) NetworkSecurity
トポロジカルソートの降順に処理を行う。自分が接続しているかつ、自分が接続しているクライアントが接続していないサーバーとの間にゲートを設置する。
#include <string> #include <vector> #include <set> using namespace std; class NetworkSecurity{public: int secureNetwork( vector <string> clientCable, vector <string> serverCable ) { int N = (int)clientCable[0].length(); int M = (int)serverCable[0].length(); vector<bool> secure( N ); vector<vector<bool> > connect( N, vector<bool>( M ) ); int gate = 0; while ( true ) { // 接続先のクライアントが全てセキュアなクライアントを探す int cur; for( cur=0; cur<N; cur++ ) if ( ! secure[cur] ) { bool f = true; for ( int i=0; i<N; i++ ) if ( clientCable[cur][i] == 'Y' && ! secure[i] ) f = false; if ( f ) break; } if ( cur >= N ) break; // このクライアントは接続しているが、 // 接続先のクライアントは接続していないサーバー間にゲートを設置 for ( int i=0; i<M; i++ ) if ( serverCable[cur][i] == 'Y' ) { bool f = true; for ( int j=0; j<N; j++ ) if ( clientCable[cur][j] == 'Y' && connect[j][i] ) f = false; if ( f ) gate++; } // このクライアントから接続可能なサーバーを調べる for ( int i=0; i<M; i++ ) { if ( serverCable[cur][i] == 'Y' ) connect[cur][i] = true; for ( int j=0; j<N; j++ ) if ( clientCable[cur][j] == 'Y' && connect[j][i] ) connect[cur][i] = true; } secure[cur] = true; } return gate; } };