TopCoder SRM 298 Div1 Medium OrderDoesMatter

問題

n個の行列が与えられて、それぞれの大きさはN[i]行M[i]列である。
この行列を、好きな順に並び替えて掛け算する。
（ただし、並び替えた順で積が定義されるようにしなけらばならない）

このとき、積の行列の要素の数がもっとも多くなるような並び順について、
積の行列の要素の数を求めよ。
積が定義できる並び順が存在しないとき、-1を返せ。

制約条件

n≦50
N[i],M[i]≦1000

方針

行または列の大きさの整数を頂点とするようなグラフを考える。
n行m列の行列があるとき、nからmへの有向辺を張る。

このようにして出来たグラフの、オイラー路が行列の積に対応する。
オイラー路が存在することが必要、すなわち、

• グラフが連結かつ以下のどちらかがなりたつ
• 全ての頂点の相対次数が0
• ひとつの頂点の相対次数が+1, もうひとつの頂点の相対次数が-1, その他全ての頂点の相対次数が0

が成り立たなければ-1.

オイラー路があるときは、
全ての次数が0だったら、好きな頂点を始点に出来るので、最も大きい数字頂点をスタートに選べばよい。
そうでない場合、オイラー路は一通りになるので、積も一通りになる。

ソースコード

bool e[1001][1001], v[1001];
int deg[1001];

struct OrderDoesMatter{
	int getOrder(vector<int> N, vector<int> M){
		int n=N.size();
		for(int i=0;i<n;i++){
			e[N[i]][M[i]]=1;
			deg[N[i]]++;
			deg[M[i]]--;
		}
		int nz=0, pi=N[0], mi=N[0];
		for(int i=0;i<=1000;i++)if(deg[i]!=0){
			nz++;
			if(abs(deg[i])!=1)return -1;
			if(deg[i]<0)mi=i;
			if(deg[i]>0)pi=i;
		}
		if(nz>2)return -1;
		rec(pi);
		for(int i=0;i<n;i++)if(!v[N[i]])return -1;
		
		if(nz)return mi*pi;
		int ans=0;
		for(int i=0;i<n;i++)ans=max(ans,N[i]*N[i]);
		return ans;
	}
	
	void rec(int c){
		v[c]=1;
		for(int i=0;i<=1000;i++)if(e[c][i]&&!v[i])rec(i);
	}
};