Codeforces #234 Div2. D. Dima and Bacteria

変な設定の問題。
http://codeforces.com/contest/400/problem/D

問題

N個の細菌があり、それらはK個のグループに分類できる。
N個の細菌はのうち幾つかの対(u[i],v[i])において、それらの細菌はコストx[i]で相互に変換できる。

上記グループ分類と相互変換ルールが与えられたとき：

• 同一グループ内の細菌はすべてコスト0で相互に変換可能か
• 上記を満たす場合、あるグループの細菌が別のグループの細菌に至る最小コストを答えよ。

解法

答え方が2段階あるので個々に答えていく。
前者については、相互変換ルールのうちコスト0のものを用いて細菌同士をUnion-findで連結していけばよい。
同一グループに属しているはずなのに、Union-findで同値扱いできない細菌がある場合は答えは変換できない、となる。

変換できる場合、グループ内の細菌の変換コストは0となる。
そのため、細菌u[i]、v[i]が属するグループをC[u[i]]、C[v[i]]とすると、(u[i],v[i])の細菌の変換ルールは(C[u[i]],C[v[i]])とグループ間の変換ルールとみなすことができる。
後は、これらグループ間でワーシャルフロイト法を実行してグループ間の最小変換コストを求めればよい。

const int ufmax=1000001;
int ufpar[ufmax],ufrank[ufmax];
void UF_init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; } }
int UF_find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = UF_find(ufpar[x]));}
void UF_unite(int x,int y) {
	x = UF_find(x); y = UF_find(y);
	if(x==y) return;
	if(ufrank[x]<ufrank[y]) ufpar[x]=y;
	else {ufpar[y]=x; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
}

int N,M,K;
int C[1000],S[1000],E[1000];
int T[100001];
vector<int> SE[100001];
ll mat[501][501];
int vis[100001];


void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>K;
	l=0;
	FOR(i,K) {
		cin>>C[i];
		S[i]=l;
		FOR(j,C[i]) T[l++]=i;
		E[i]=l;
	}
	FOR(x,K) FOR(y,K) mat[x][y]=1LL<<50;
	FOR(x,K) mat[x][x]=0;
	UF_init();
	
	FOR(i,M) {
		cin>>x>>y>>j;
		if(j==0) UF_unite(x-1,y-1);
		if(T[x-1]!=T[y-1]) {
			mat[T[x-1]][T[y-1]] = min(mat[T[x-1]][T[y-1]],(ll)j);
			mat[T[y-1]][T[x-1]] = min(mat[T[y-1]][T[x-1]],(ll)j);
		}
	}
	
	FOR(i,K) {
		for(j=S[i];j<E[i];j++) if(UF_find(j)!=UF_find(S[i])) return _P("No\n");
	}
	
	FOR(j,K) FOR(x,K) FOR(y,K) mat[x][y]=min(mat[x][y],mat[x][j]+mat[j][y]);
	FOR(x,K) FOR(y,K) if(mat[x][y]==1LL<<50) mat[x][y]=-1;
	_P("Yes\n");
	FOR(x,K) {
		FOR(y,K) _P("%lld ",mat[x][y]);
		_P("\n");
	}
	
}

まとめ

2段階で答えさせるとは変な問題だ。