cf444E. DZY Loves Planting(并查集)
程序员文章站
2022-10-16 16:48:21
题意 "题目链接" Sol 神仙题啊Orzzzzzz 考场上的时候直接把树扔了对着式子想,想1h都没得到啥有用的结论。 然后cf正解居然是网络流??出给NOIP模拟赛T1???¥%……&((……%&(( 说一下非网络流解法吧。 首先题目中给出的$g(i, p_i)$我们可以认为是对于每个节点$i$, ......
题意
sol
神仙题啊orzzzzzz
考场上的时候直接把树扔了对着式子想,想1h都没得到啥有用的结论。
然后cf正解居然是网络流??出给noip模拟赛t1???¥%……&((……%&((
说一下非网络流解法吧。
首先题目中给出的\(g(i, p_i)\)我们可以认为是对于每个节点\(i\),分配一个节点\(p_i\),同时还有数量\(x_i\)的限制
同时题目中要求的是最小值最大,不难想到二分答案。但其实只要把边从小到大排序,依次考虑每条边能否成为答案就行了
用并查集维护节点之间的联通性,对于一条边来说,如果这条边可以成为答案,那么对于当前已经合并的每个点,我们都需要给它分配一个未被合并的点(注意这里边权是已经排好序的)
维护\(siz[x]\)表示\(x\)节点的连通块的大小,\(sum = \sum_{i = 1}^n x_i\), \(f[x]\)表示已经合并的节点的\(x_i\)之和(也就是不能使用的点)
那么一条边可以被合并的条件为\(siz[x] <= sum - f[x]\)
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, fa[maxn], x[maxn], siz[maxn], sum; struct edge { int u, v, w; bool operator < (const edge &rhs) const { return w < rhs.w; } }e[maxn]; int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } int main() { n = read(); for(int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1; for(int i = 1; i <= n - 1; i++) e[i].u = read(), e[i].v = read(), e[i].w = read(); sort(e + 1, e + n); for(int i = 1; i <= n; i++) x[i] = read(), sum += x[i]; for(int i = 1; i <= n - 1; i++) { int fx = find(e[i].u), fy = find(e[i].v); if(fx == fy) continue; fa[fy] = fx; siz[fx] += siz[fy]; x[fx] += x[fy]; if(siz[fx] > sum - x[fx]) {printf("%d\n", e[i].w); return 0;} } printf("%d\n", e[n - 1].w); return 0; }
上一篇: android 百度地图自定义圆,更改默认图标等常用方法
下一篇: iOS的手势识别器