TopCoder SRM 549 Div2 Hard OrderOfTheHats

今回は自力で解けずにEditorialを見て解答。
http://community.topcoder.com/stat?c=problem_statement&pm=11955

問題

N種類の魔法がある。
一部の魔法は習得するために、先行して他の魔法を習得しておく必要があり、その依存関係が行列の形で与えられる。

依存関係が循環している場合、全ての魔法を習得できない。
循環した依存関係を解消し、全ての魔法を習得するために書き換える必要がある行列の要素数を最小化せよ。

解法

依存関係を有向辺で表すと、この問題は「有向グラフから閉路をなくすために取り除く辺を最少化せよ」となる。

閉路がないということは点をトポロジカルな順に並べ替えることができる。
逆に、トポロジカル順に逆らうような辺を削除することで点をトポロジカルソートが可能になるので、点をトポリジカル順に並べていき、削除する辺の数を減らしていけばよい。

すでに点をトポロジカル順に並べた配列に加えたか、まだ加えてないかをbitmapで管理し、bitDPで点を加えつつ削除する辺の数を数えていく。

int N;
int mat[21][21];
int mask[1<<20];

class OrderOfTheHats {
	public:
	
	
	int minChanged(vector <string> spellChart) {
		int x,y,i,j,r;
		
		N=spellChart.size();
		FOR(y,N) FOR(x,N) mat[y][x]=spellChart[y][x]=='Y';
		
		FOR(i,1<<N) mask[i]=99999;
		mask[0]=0;
		FOR(i,1<<N) {
			FOR(j,N) {
				if(i & (1<<j)) continue;
				r=0;
				FOR(x,N) if((i & (1<<x))||j==x) r += mat[j][x];
				mask[i | (1<<j)] = min(mask[i | (1<<j)], mask[i] + r);
			}
		}
		return mask[(1<<N)-1];
	}
};

まとめ

沢山辺があったら閉路もたくさんできてどうしようと悩んだが、あっさり解けるものなのね…。
このテクニックは応用効きそうだから覚えておこう。