問題
http://community.topcoder.com/stat?c=problem_statement&pm=12946&rd=15836
有向グラフが与えられる。
各ノードについてはコストを持つ。
２人のプレイヤーがゲームを行い、各ターンごとにグラフを２つに分割し、
好きな方の１つを消すことができる。
最初のプレイヤーはできるだけ最後に残るノードのコストを大きくしたく、
２人目のプレイヤーはできるだけ小さくしたい。
このとき、最後に残るノードの最大コストを求める。
解き方
２人ゲームなので必勝法を考察する。
今回は間にあるノードを残したくても、相手のターンで必ず消されてしまう。
逆に端にあるノードは必ず残すことができる。
よって、端にあるノードのうち最大のものが答えになる。
コード
class MaxMinTreeGame {
public: int findend(vector<int> edges, vector<int> costs) {
int n=costs.size();
int d[n][n];
memset(d,0,sizeof(d));
FORE(i,0,edges.size()){
d[edges[i]][i+1]=1;
d[i+1][edges[i]]=1;
}
int ret=0;
FORE(i,0,n){
int cnt=0;
FORE(j,0,n)if(d[i][j])cnt++;
if(cnt<=1)ret=max(ret,costs[i]);
}
return ret;
}
};
public: int findend(vector<int> edges, vector<int> costs) {
int n=costs.size();
int d[n][n];
memset(d,0,sizeof(d));
FORE(i,0,edges.size()){
d[edges[i]][i+1]=1;
d[i+1][edges[i]]=1;
}
int ret=0;
FORE(i,0,n){
int cnt=0;
FORE(j,0,n)if(d[i][j])cnt++;
if(cnt<=1)ret=max(ret,costs[i]);
}
return ret;
}
};