BZOJ 3573 [HNOI2014]米特运输

题目链接:传送门
冗长冗长的题面:

Description

米特是D星球上一种非常神秘的物质,蕴含着巨大的能量。在以米特为主要能源的D星上,这种米特能源的运输和储存一直是一个大问题。D星上有N个城市,我们将其顺序编号为1到N,1号城市为首都。这N个城市由N-1条单向高速通道连接起来,构成一棵以1号城市(首部)为根的树,高速通道的方向由树中的儿子指向父亲。树按深度分层:根结点深度为0,属于第1层;根结点的子节点深度为1,属于第2层;依此类推,深度为i的结点属于第i+l层。建好高速通道之后,D星人开始考虑如何具体地储存和传输米特资源。由于发展程度不同,每个城市储存米特的能力不尽相同,其中第i个城市建有一个容量为A[i]的米特储存器。这个米特储存器除了具有储存的功能,还具有自动收集米特的能力。如果到了晚上六点,有某个储存器处于未满的状态,它就会自动收集大气中蕴含的米特能源,在早上六点之前就能收集满;但是,只有在储存器完全空的状态下启动自动收集程序才是安全的,未满而又非空时启动可能有安全隐患。早上六点到七点间,根节点城市(1号城市)会将其储存器里的米特消耗殆尽。根节点不会自动搜集米特,它只接受子节点传输来的米特。早上七点,城市之间启动米特传输过程,传输过程逐层递进:先是第2层节点城市向第1层(根节点城市,即1号城市)传输,直到第1层的储存器满或第2层的储存器全为空;然后是第3层向第2层传输,直到对于第2层的每个节点,其储存器满或其予节点(位于第3层)的储存器全为空;依此类推,直到最后一层传输完成。传输过程一定会在晚上六点前完成。
由于技术原因,运输方案需要满足以下条件:
(1)不能让某个储存器到了晚上六点传输结束时还处于非空但又未满的状态,这个时候储存器仍然会启动自动收集米特的程序,而给已经储存有米特的储存器启动收集程序可能导致危险,也就是说要让储存器到了晚上六点时要么空要么满;
(2)关于首都——即1号城市的特殊情况, 每天早上六点到七点间1号城市中的米特储存器里的米特会自动被消耗殆尽,即运输方案不需要考虑首都的米特怎么运走;
(3)除了1号城市,每个节点必须在其子节点城市向它运输米特之前将这座城市的米特储存器中原本存有的米特全部运出去给父节点,不允许储存器中残存的米特与外来的米特发生混合;
(4)运向某一个城市的若干个来源的米特数量必须完全相同,不然,这些来源不同的米特按不同比例混合之后可能发生危险。
现在D星人已经建立好高速通道,每个城市也有了一定储存容量的米特储存器。为了满足上面的限制条件,可能需要重建一些城市中的米特储存器。你可以,也只能,将某一座城市(包括首都)中原来存在的米特储存器摧毁,再
新建一座任意容量的新的米特储存器,其容量可以是小数(在输入数据中,储存器原始容量是正整数,但重建后可以是小数),不能是负数或零,使得需要被重建的米特储存器的数目尽量少。

Input

第一行是一个正整数N,表示城市的数目。
接下来N行,每行一个正整数,其中的第i行表示第i个城市原来存在的米特储存器的容量。
再接下来是N-I行,每行两个正整数a,b表示城市b到城市a有一条高速通道(a≠b)。
N<500000,A[j]<10^8

Output

输出文件仅包含一行,一个整数,表示最少的被重建(即修改储存器容量)的米特储存器的数目。

Sample Input

5
5
4
3
2
1
1 2
1 3
2 4
2 5

Sample Output

3

【样例解释】

一个最优解是将A[1]改成8,A[3]改成4,A[5]改成2。
这样,2和3运给1的量相等,4和5运给2的量相等,且每天晚上六点的时候,1,2满,3,4,5空,满足所有限制条件。

这题最大的难度就是读懂题了
反正对我来说是这样的,,
然后就有了一句话题面
要求在一颗树上修改一些点的权值使得:父节点的所有子节点权值必须相同、父节点的权值必须是所有子节点的权值之和
要求最少的修改次数
这样就很明显了
只要树上有一个点的权值确定了
这棵树的所有点的权值就都知道了
就是用最多的点确定一颗树
要求父节点的权值是子节点的子节点个数倍
所以累计权值就好了
但是
这样乘起来会爆long long
叹服前人的智慧
底数看你心情
然后我们就可以用愉快的把它们加起来了
最后排序找相同最多的就好了
注意表示确定了点后根节点的权值
至此。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <vector>
#include <iomanip>
#define A 1000010
#define B 2010
#define ll long long

using namespace std;
struct node {
    int next, to;
}edge[A];
int head[A], num_edge;
double cnt[A];
void add_edge(int from, int to) {
    edge[++num_edge].next = head[from];
    edge[num_edge].to = to;
    head[from] = num_edge;
}
double w[A], f[A];
int n, a, b;
void dfs(int fr, double st, int fa) {
    f[fr] = st + log(w[fr]);
    for (int i = head[fr]; i; i = edge[i].next) {
        int ca = edge[i].to;
        if (ca == fa) continue;
        dfs(ca, st + log(cnt[fr]), fr);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i < n; i++) {
        cin >> a >> b;
        add_edge(a, b);
        add_edge(b, a);
        cnt[a]++;
    }
    dfs(1, log(1.0), 1);
    sort(f + 1, f + n + 1);
    int tot = 1, ans = 1;
    for (int i = 2; i <= n; i++)
      if (f[i] - f[i - 1] <= 1e-8)
        tot++, ans = max(ans, tot);
      else tot = 1;
    cout << n - ans << endl;
}
全部评论

相关推荐

06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
05-26 22:25
门头沟学院 Java
Java小肖:不会是想叫你过去把你打一顿吧,哈哈哈
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务