Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1578-30e0a7bc
この記事にトラックバックする(FC2ブログユーザー)

SRM480 DIV1 MEDIUM - NetworkSecurity (この記事を編集する[管理者用])

Source

TopCoder SRM480 DIV1 MEDIUM (450pt)
Problem Statement
SRM480 DIV1 自分の参加記録

問題概要

50個以下のクライアントと50個以下のサーバをノードとした,閉路のない有向グラフが与えられる.
いくつかの枝にセキュリティウェアをインストールしたい.
クライアントからサーバにパスがある組み全部に対して,セキュリティウェアをインストールしたノードを通るパスが最低1個は存在するようにしたい.
インストールする数の最小値を求める問題.

解法

クライアント・サーバ間の枝にのみインストールすれば良い.
トポロジカルソートなどをして,下流に属するノードからgreedyに繋げていく.

C++によるスパゲッティなソースコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.
(DAGであるという仮定を見逃してた時のコードです)

// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define INF 1000000000

int m,n;
int edge[60][60];
int ok[60], con[60][60], dist[60][60], deg[60];
int res;

class NetworkSecurity {
public:
int secureNetwork(vector <string> clientCable, vector <string> serverCable) {
  int i,j,k,m,n,mx,a;

  n=serverCable.size();
  m=serverCable[0].size();
  res=0;

  rep(i,n) rep(j,n) dist[i][j]=INF; rep(i,n) dist[i][i]=0;
  rep(i,n) rep(j,n) if(clientCable[i][j]=='Y') dist[i][j]=1;
  rep(k,n) rep(i,n) rep(j,n) if(dist[i][j]>dist[i][k]+dist[k][j]) dist[i][j]=dist[i][k]+dist[k][j];

  rep(i,n) rep(j,m) con[i][j]=0;

  rep(i,n) rep(j,m){
    rep(k,n) if(dist[i][k]!=INF && serverCable[k][j]=='Y') con[i][j]=1;
  }

  rep(i,n) deg[i]=0;
  rep(i,n) rep(j,n) if(dist[i][j]!=INF) deg[i]++;

  rep(k,m){
    rep(i,n) ok[i]=1;
    rep(i,n) if(con[i][k]) ok[i]=0;

    for(;;){
      mx=10000000;
      rep(i,n) if(!ok[i] && serverCable[i][k]=='Y' && deg[i]<mx) mx=deg[i], a=i;
      if(mx==10000000) break;

      res++;
      rep(i,n) if(dist[i][a]!=INF && !ok[i]) ok[i]=1;
    }
  }
 
  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1578-30e0a7bc
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。