本文主要是介绍【并查集】JZOJ_3301 家族,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意
你需要选定一个范围,边权在这个范围内的边才看做存在,若干边把图分成若干个集合,点不同数量的集合,会获得相应不同的价值。求一个最小的范围使得价值超过k。
思路
一开始以为是二分,结果多加了一个没必要的时间复杂度,这里也没有单调性可言。
利用并查集对集合进行操作,统计一下答案即可。
把边权排序可进行小小剪枝。
代码
#include<cstdio>
#include<algorithm>struct node {int u, v, f;
}edge[5001];
int n, m, k;
int a[1001], fa[1001], size[1001];int cmp(node x, node y) {return x.f < y.f;
}int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);
}int main() {scanf("%d %d %d", &n, &m, &k);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);int mins = 2147483647, maxs = 0;for (int i = 1; i <= m; i++)scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].f);std::sort(edge + 1, edge + 1 + m, cmp);int f = 0, ans = 2147483647;long long sum = 0;for (int i = 1; i <= m; i++) {sum = 0;for (int xx = 1; xx <= n; xx++)fa[xx] = xx, size[xx] = 1, sum += a[1];for (int j = i; j <= m; j++) {if (edge[j].f - edge[i].f > ans) break;long long f1 = find(edge[j].u), f2 = find(edge[j].v); if (f1 == f2) continue;sum = sum - a[size[f1]] - a[size[f2]] + a[size[f1] + size[f2]];fa[f1] = f2;size[f2] += size[f1];if (sum >= k) {ans = std::min(ans, edge[j].f - edge[i].f);f = 1;break;}}}f ? printf("%d", ans) : printf("T_T");
}
这篇关于【并查集】JZOJ_3301 家族的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!