设为首页 加入收藏

TOP

cfE. Ehab and a component choosing problem(贪心)
2018-12-05 12:09:21 】 浏览:11
Tags:cfE. Ehab and component choosing problem 贪心

题意

题目链接

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

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

Sol

结论:选出的\(k\)个联通块的大小是一样的且都等于最大联通块的大小

证明:因为我们是在保证分数最大的情况下才去最大化\(k\),一个很经典的结论是单独选择一个权值最大的联通块得到的分数一定是最大的,然后我们这时我们才去考虑最大化\(k\)

那么思路就很清晰了,先一遍dfs dp出最大联通块,然后再一遍dfs从下往上删就行了

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int MAXN = 3e5 + 10, INF = 1e18;
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, a[MAXN], mx[MAXN], ans = -INF, num;
#define siz(v) ((int)v.size())
vector<int> v[MAXN];
void dfs(int x, int fa) {
    mx[x] = a[x];
    for(int i = 0; i < siz(v[x]); i++) {
        int to = v[x][i];
        if(to == fa) continue;
        dfs(to, x);
        mx[x] = max(mx[x], mx[x] + mx[to]);
    }
    ans = max(ans, mx[x]);
}
void dfs2(int x, int fa) {
    mx[x] = a[x];
    for(int i = 0; i < siz(v[x]); i++) {
        int to = v[x][i];
        if(to == fa) continue;
        dfs2(to, x);
        mx[x] = max(mx[x], mx[x] + mx[to]);
    }
    if(mx[x] == ans) num++, mx[x] = 0;
}
signed main() {
#ifndef ONLINE_JUDGE
    //freopen("a.in", "r", stdin);freopen("a.out", "w", stdout);
#endif
    N = read();
    for(int i = 1; i <= N; i++) a[i] = read();
    for(int i = 1; i <= N - 1; i++) {
        int x = read(), y = read();
        v[x].push_back(y); v[y].push_back(x);
    }
    dfs(1, 0); 
    //printf("%I64d\n", ans);
    memset(mx, 0, sizeof(mx));
    dfs2(1, 0);
    cout << ans * num << " " << num;
    return 0;
}

编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇BZOJ4513: [Sdoi2016]储能表(数位.. 下一篇BZOJ4602: [Sdoi2016]齿轮(并查集..

评论

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

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