c/c++语言开发共享cf444E. DZY Loves Planting(并查集)

题意

题目链接

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("%dn", e[i].w); return 0;}     }     printf("%dn", e[n - 1].w);     return 0; }