SRM 640 DIV1 Easy - ChristmasTreeDecoration (○)

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13551&rd=16083

・クリスマスツリーをデコレーションするのに、N個の星とN-1個のリボンがある。
・星には色がついていて、全ての星をリボンで一つにつなげたい。
・ただし、できるだけリボンでつなげるときの星の色は異なるようにしたい。
・また、つなぐことのできる星のペアもわかっている。
・このとき、同じ色同士の星をつなげるリボンの最小数を求める。

解き方


・ぱっと見て、ダイクストラ法に見える。
・ただし、ダイクストラでつなげていって最後に同じ色同士の星しかつなげられない場合、
 つなげた星によって解が異なってしまう。

・よって、まずは部分的につながっていなくて、かつ異なる色の星をつなげていく。
・そのような星がなくなったら、同じ色の星をつなげる。

・集合を使おうかと思ったが、ワーシャルフロイドで計算量は
 50*50*50*50=25*25*10000=625*10^4=6.25*10^6で間に合う。

→System Passed

コード


using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class ChristmasTreeDecoration {

public: int solve(vector<int> col, vector<int> x, vector<int> y) {
int n=col.size();
int d[n][n];
memset(d,0,sizeof(d));

int ret=0;
FORE(p,0,n-1){
FORE(k,0,n)FORE(i,0,n)FORE(j,0,n)d[i][j]|=(d[i][k]&d[k][j]);

int invalid=1;
FORE(i,0,x.size())if(d[x[i]-1][y[i]-1]==0 && col[x[i]-1]!=col[y[i]-1]){
d[x[i]-1][y[i]-1]=1;
invalid=0;
break;
}

if(invalid)FORE(i,0,x.size())if(d[x[i]-1][y[i]-1]==0){
d[x[i]-1][y[i]-1]=1;
ret++;
break;
}
}

return ret;
}

};
このエントリーをはてなブックマークに追加