TopCoder SRM 687 Div1 Medium AllGraphCuts

微妙な制限のためResubmit。
https://community.topcoder.com/stat?c=problem_statement&pm=14214

問題

N頂点の容量付無向グラフの全頂点対(x,y)に対する最小カットの値X(x,y)が与えられる。
そのような最小カットを与えるグラフが存在するなら、一例を示せ。
ただし辺の数は1000以下であること。

解法

以下を知っていると楽だったようだが、知らなくても何とか解けた。
ゴモリ・フー木 - Wikipedia

まず自明に不可な場合(X(a,b)!=0やX(a,b)!=X(b,a))の場合は存在しない。
他の場合、以下の手順で木として題意を満たすグラフを構築できる。

まず全頂点対を最小カットの大きい順に処理しよう。
頂点対(a,b)を順に見たとき、その２頂点間がすでに連結している場合、その２頂点間は最低でもX(a,b)以上のフローが流せるのでそれ以上何もしない。
逆に非連結なら、両者を容量X(a,b)の辺でつなぐ。

そして最終的にできたグラフが解。
Union-Findで連結判定をしても良いようだが、自分は毎回Warshall-Floyedを実行し、生成したグラフの最大フローを再計算した。
（グラフが木なので、最大フローは経路中の最小容量辺で決まるため、WFで容易に計算できる）

容量0の辺を張っても良いが、全頂点対に辺を張ると計1225本の辺を張ることになり、問題の条件から外れる。
これのせいでResubmitするハメになった。

int mat[51][51];
int ma[51][51];


class AllGraphCuts {
	public:
	vector <int> findGraph(vector <int> X) {
		int N=0,x,y,z;
		while(N*N<X.size()) N++;
		FOR(y,N) FOR(x,N) mat[y][x]=X[y*N+x];
		vector<pair<int,int>> E;
		FOR(y,N) FOR(x,N) {
			if(x==y && mat[x][x]) return {-1};
			if(mat[x][y]!=mat[y][x]) return {-1};
			if(x<y) E.push_back({mat[x][y],x*100+y});
		}
		ZERO(ma);
		
		sort(E.begin(),E.end());
		reverse(E.begin(),E.end());
		FOR(x,N) FOR(y,N) ma[x][y]=-1;
		FOR(x,N) ma[x][x]=100000;
		vector<int> v;
		FORR(r,E) {
			x=r.second/100;
			y=r.second%100;
			if(ma[x][y]>=0) continue;
			ma[x][y]=ma[y][x]=r.first;
			v.push_back(r.first*N*N+y*N+x);
			FOR(z,N) FOR(x,N) FOR(y,N) ma[x][y]=max(ma[x][y],min(ma[x][z],ma[z][y]));
		}
		
		FOR(y,N) FOR(x,N) if(x!=y && ma[x][y]!=mat[x][y]) return {-1};
		
		return v;
	}
}

まとめ

辺の数が1000以下って条件いるのかなぁ…。
N*(N-1)/2以下で良かったのに。