设为首页 加入收藏

TOP

BZOJ4602: [Sdoi2016]齿轮(并查集 启发式合并)
2018-12-05 12:09:21 】 浏览:49
Tags:BZOJ4602: Sdoi2016 齿轮 查集 启发式 合并

题意

题目链接

给出一棵树,每个节点有权值,选出\(k\)个联通块,最大化

\[\frac{\sum_{i \in S} a_i}{k}\]

Sol

和cc的一道题很像啊

对于初始的\(N\)个点,每加一条限制实际上就是合并了两个联通块。

那么我们预处理出\(val[i]\)表示的是\(i\)节点所在的联通块根节点转了\(1\)圈,该节点会转多少圈

并查集维护联通性以及联通块大小,直接启发式合并就可以了

跑的好像还挺快

#include<bits/stdc++.h>
#define siz(v) ((int)v.size())
using namespace std;
const int MAXN = 2001;
const double eps = 1e-9;
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, M, fa[MAXN], siz[MAXN];
double val[MAXN];
vector<int> v[MAXN];
void init() {
    for(int i = 1; i <= N; i++) fa[i] = i, v[i].clear(), siz[i] = 1, val[i] = 1;
}
int find(int x) {
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}
bool dcmp(double x) {
    return fabs(x) < eps;
}
void mem(int x, int fa, double va) {
    for(int i = 0; i < siz(v[x]); i++) {
        int to = v[x][i];
        if(to == fa) continue;
        val[to] *= va;
        mem(to, x, va);
    }
}
bool solve() {
    N = read(); M = read(); bool flag = 0;   
    init();
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read(), fx = find(x), fy = find(y); double vx = read(), vy = read();
        if(flag) continue;
        if(fx == fy) {if(!(dcmp(val[x] / val[y] - vx / vy))) flag = 1; continue;}
        if(siz[fx] > siz[fy]) swap(x, y), swap(v
		    

x, vy), swap(fx, fy); val[fx] = vx / vy * val[y] / val[x]; mem(fx, 0, val[fx]); fa[fx] = fy; v[y].push_back(fx); siz[fy] += siz[fx]; siz[fx] = 0; } return flag ^ 1; } int main() { #ifndef ONLINE_JUDGE freopen("a.in", "r", stdin); #endif int T = read(); for(int i = 1; i <= T; i++) { printf("Case #%d: ", i); puts(solve() ? "Yes" : "No"); } return 0; } /* 2 3 3 1 2 3 5 2 3 5 -7 1 3 3 7 3 3 1 2 3 5 2 3 5 -7 1 3 3 -7 */

编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇cfE. Ehab and a component choos.. 下一篇(杭电 1097)A hard puzzle

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }