Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM557 DIV1 MEDIUM (550pt)
Problem Statement

問題概要

n人の少女がいる.(50以下)
また,各少女が,各少女が愛しているかどうかが与えられる.
好きな少女を魔法少女にすることができる.
魔法少女になると,魔法少女が愛している少女を守ることができて,また,守られている少女が好きな少女も守られる.
守られていない魔法少女の数の最大値を求める問題.

解法

各少女について,その少女が魔法少女になれば結果的に守られる少女を調べるために,ワーシャルフロイドやら何やらしておく.
魔法少女になったら,自分を守ることになる少女は,魔法少女にするだけ損なので除外して考える.
するとグラフはDAGになって,最小パス被覆を求める問題になって,二部マッチングで解ける.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

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

#define INT_INF 1000000000

#define INT_LIST_MAX_FLOW_NODE 102
int intLmfEdge[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfFlow[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfInv[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfEdgeSize[INT_LIST_MAX_FLOW_NODE],intLmfEdgeMemory[INT_LIST_MAX_FLOW_NODE];
int intLmfLevel[INT_LIST_MAX_FLOW_NODE];
int intLmfQueue[INT_LIST_MAX_FLOW_NODE];

void intListMaxFlowLevelize(int n,int st,int ed){
  int i,j,k,t;
  int q_st,q_end;
  rep(i,n) intLmfLevel[i]=-1; intLmfLevel[st]=0; q_st=0; q_end=1; intLmfQueue[0]=st;
  while(q_st!=q_end){
    i=intLmfQueue[q_st++]; t=intLmfLevel[i]+1;
    rep(j,intLmfEdgeSize[i]) if(intLmfFlow[i][j]){
      k=intLmfEdge[i][j]; if(intLmfLevel[k]!=-1) continue;
      intLmfLevel[k]=t; intLmfQueue[q_end++]=k; if(k==ed) return;
    }
  }
}

int intListMaxFlowFlow(int i,int ed,int lim){
  int j,k,ret=0,t,s,ji;
  if(i==ed) return lim;
  rep(j,intLmfEdgeSize[i]) if(intLmfFlow[i][j]){
    k=intLmfEdge[i][j]; if(intLmfLevel[k]<=intLmfLevel[i]) continue;
    s=lim; if(s>intLmfFlow[i][j]) s=intLmfFlow[i][j];
    t=intListMaxFlowFlow(k,ed,s); if(!t) continue;
    ret+=t; lim-=t; ji=intLmfInv[i][j];
    intLmfFlow[i][j]-=t; intLmfFlow[k][ji]+=t;
    if(!lim) break;
  }
  if(lim) intLmfLevel[i]=-1;
  return ret;
}

int intListMaxFlow(int n,int st,int ed){
  int ret=0;
  for(;;){
    intListMaxFlowLevelize(n,st,ed); if(intLmfLevel[ed]==-1) break;
    ret += intListMaxFlowFlow(st,ed,INT_INF);
  }
  return ret;
}

void intListMaxFlowEdgeInit(){
  int i;
  rep(i,INT_LIST_MAX_FLOW_NODE) intLmfEdgeSize[i]=0;
}

void intListMaxFlowEdgeInitAdv(int n){
  int i;
  rep(i,n) intLmfEdgeSize[i]=0;
}

void intListMaxFlowEdgeAdd(int n1,int n2,int f1,int f2){
  int s1=intLmfEdgeSize[n1]++, s2=intLmfEdgeSize[n2]++;
  intLmfEdge[n1][s1]=n2; intLmfEdge[n2][s2]=n1;
  intLmfFlow[n1][s1]=f1; intLmfFlow[n2][s2]=f2;
  intLmfInv[n1][s1]=s2;  intLmfInv[n2][s2]=s1;
}

int n;
vector<string> in;

class Incubator {
public:
int maxMagicalGirls(vector <string> in_baka) {
  int i,j,k;
  int ind[60];
  int node, st, ed;
  int res = 0;

  in = in_baka;
  n = in.size();
  rep(k,n) rep(i,n) rep(j,n) if(in[i][k]=='Y' && in[k][j]=='Y') in[i][j] = 'Y';

  for(;;){
    int fg = 0;
    rep(k,n) if(in[k][k]=='Y'){
      n--; fg = 1;
      in.erase(in.begin() + k);
      rep(i,n) in[i].erase(in[i].begin() + k);
      break;
    }
    if(!fg) break;
  }

//  rep(i,n) cout << in[i] << endl;

  node = 2*n;
  st = node++; ed = node++;
  intListMaxFlowEdgeInitAdv(node);

  rep(i,n) rep(j,n) if(in[i][j]=='Y') intListMaxFlowEdgeAdd(i,n+j,1,0);
  rep(i,n) intListMaxFlowEdgeAdd(st,i,1,0);
  rep(i,n) intListMaxFlowEdgeAdd(i+n,ed,1,0);

  res = n - intListMaxFlow(node, st, ed);

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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