Codeforces 400D Dima and Bacteria(Floyd+并查集）

题目链接：Codeforces 400D Dima and Bacteria

题目大意：给出n，m和k，表示有n个细菌，m种仪器和k种细菌，给出k种细菌的数量ci，然后每个细菌按照种类排成一排（所以有第i种细菌的序号从∑（1≤j≤i-1）cj + 1 到∑（1≤j≤i）cj）；接下来给出m种仪器，有u，v，x三个值，表示说从可以在第u，v号细菌之间移动能量，代价为x。请帮助博士判断说这些细菌是否正确，正确的前提条件是说同种细菌之间移动能量为0，如果正确的话，给出两两细菌（种类）间移动能量的最小值。

解题思路：题目有点长，琢磨了很久，要注意的是当前细菌可以先移动到其它细菌上。我的做法是，如果当前仪器x为0，就将两个序号的细菌连接连接（并查集），然后在判断是否正确的时候，只要同一种细菌处于同以集合即可。然后处理最短路径就用Floyd算法。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
const int N = 1e5+5;
const int K = 505;
const int INF = 0x3f3f3f3f;

int n, m, k, t[N], f[N];
int c[K], d[K][K];

int getfar(int x) {
	return x == f[x] ? x : f[x] = getfar(f[x]);
}

void init () {
	scanf("%d%d%d", &n, &m, &k);
	memset(d, INF, sizeof(d));
	for (int i = 1; i <= n; i++) f[i] = i;

	int p = 1, u, v, x;
	for (int i = 1; i <= k; i++) {
		scanf("%d", &c[i]);
		for (int j = 0; j < c[i]; j++) t[p++] = i;
	}

	for (int i = 0; i < m; i++) {
		scanf("%d%d%d", &u, &v, &x);

		int ui, vi;
		if (x == 0) {
			ui = getfar(u);
			vi = getfar(v);
			if (ui != vi) f[vi] = ui;
		}

		ui = t[u]; vi = t[v];
		d[ui][vi] = d[vi][ui] = min(d[ui][vi], x);
	}
}

bool judge () {

	int p = 1;
	for (int i = 1; i <= k; i++) {
		int u = getfar(p);
		for (int j = 0; j < c[i]; j++) {
			int v = getfar(p);
			if (v != u) return false;
			p++;
		}
	}
	return true;
}

void solve () {
	for (int i = 1; i <= k; i++) d[i][i] = 0;

	for (int x = 1; x <= k; x++) {
		for (int i = 1; i <= k; i++) {
			for (int j = 1; j <= k; j++) {
				d[i][j] = min(d[i][j], d[i][x] + d[x][j]);
			}
		}
	}
}

int main () {
	init ();
	if (judge()) {
		solve ();
		printf("Yes\n");
		for (int i = 1; i <= k; i++) {
			for (int j = 1; j < k; j++) printf("%d ", d[i][j] != INF ? d[i][j] : -1);
			printf("%d\n", d[i][k] != INF ? d[i][k] : -1);
		}
	} else
		printf("No\n");
	return 0;
}