Good Bye 2014 : B. New Year Permutation

Good Bye 2014に参加。
ABCDをサクサク解いて早々に6Hack決めたものの、Eのバグとりが間に合わず微妙な順位。
幸い、参加者が多かったこともあり順位の割にレート微増で年内を赤で締めることができた。
http://codeforces.com/contest/500/problem/B

問題

1～Nのpermutationである数列P[i]が与えられる。
ここで２要素の交換を繰り返し、P[i]をできるだけ辞書順で小さな数列にしたい。
ただし、数列の任意の２要素を交換することは出来ず、交換可能な要素の対は行列A[i][j]で与えられる。

変換可能な辞書順最小の数列を求めよ。

解法

Union-FindまたはWarshall-Floyedを用いて、交換を繰り返して結果的に交換できる２要素の対を求める。
あとは数列の先頭から順に、交換可能な要素のうち最小値を持ってくるだけ。

最初にUnion-FindやWarshall-Floyedを行っておかないと、以下の1のように一旦後ろの要素に移動してから前に持ってくるケースに対応できない。
実際これで5Hackした。

3
2 1 3
001
001
110

int N;
int B[400];
int A[400][400];

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N) cin>>B[i];
	FOR(y,N) {
		cin>>s;
		FOR(x,N) A[y][x]=s[x]-'0';
	}
	FOR(i,N) FOR(x,N) FOR(y,N) A[x][y] |= A[x][i]&&A[i][y];
	FOR(x,N) {
		for(y=x+1;y<N;y++) if(A[x][y]) {
			if(B[x]>B[y]) swap(B[x],B[y]);
		}
	}
	FOR(i,N) _P("%d ",B[i]);
	_P("\n");
	
}

まとめ

まだここらへんはDiv2B相当で簡単。