本文主要是介绍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);}} elseprintf("No\n");return 0;
}
这篇关于Codeforces 400D Dima and Bacteria(Floyd+并查集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
