Accumulation Degree题解-程序员宅基地

原题传送门
题目大意：有一个树形的水系，其中有 $n$ 个节点，有 $n - 1$ 条边。 $x$ , $y$ 两点之间的容量用 $c (x, y)$ 表示。 $n$ 个点中有一个点可以作为源点，可以不断地~~流出水~~。所有度数为 $1$ 的点都为汇点，水可以从该点流出。然后求以哪个点作为源点可以使得整个水系的流量最大。

先来考虑暴力，我们取每个点为源点，然后这个就成了个有根树。

在这里插入图片描述

现在以第 $6$ 号节点为源点

在这里插入图片描述

不难发现，每个点都是从它的父亲节点获得水，并流向它的儿子节点

用 $D [x]$ 来表示以 $x$ 为根的子树中，从 $x$ 出发流向子树的最大流量
$D[x]=\sum_{y\in Son(x)}\begin{cases} min(D[y],c(x,y))& y的度数>1\\ c(x,y)& y的度数=1 \end{cases}$
对于我们要枚举的每个源点 $s$ ,可以用树形DP求出 $D [x]$ 数组

void dp(int x)
{
    
    v[x]=1;//访问标记
    d[x]=0;
    for(int i=Link[x];i;i=a[i].Next)
    {
    
        int y=a[i].y;
        if(v[y])
        {
    
            continue ;
        }
        dp(y);
        int v=a[i].v;
        if(deg[y]==1)
        {
    
            d[x]+=v;
        }
        else
        {
    
            d[x]+=min(d[y],v);
        }
    }
}

但是枚举每个根节点的复杂度是承受不了的。

此时我们就得用不那么暴力的换根法

用二次扫描与换根法代替源点的枚举

先任选一个源点为根节点，设该点为 $r o o t$ ，用上面的函数跑一遍，得到 $D_{root}$

设 $F [x]$ 为把 $x$ 作为源点的最大流量。对于我们设的根节点 $r o o t$ ,显然有 $D [r o o t] = F [r o o t]$

若 $F [x]$ 已经知道了，则考虑其子节点 $y$ , $F [y]$ 分为两部分：

1.从 $y$ 流向以 $y$ 为根的子树的流量，已经计算并存在 $D [y]$ 中了

2.从 $y$ 沿着父亲节点的路线，流到其他的节点。

在这里插入图片描述

因为把 $x$ 作为源点的总流量为 $F [x]$ ,从 $x$ 流向 $y$ 的流量为 $m i n (D [y], c (x, y))$ ，所以从 $x$ 流向除 $y$ 以外的其他部分的流量就是它们的差。

因此将 $y$ 作为源点，先流到 $x$ ，再流向其他部分的流量就是这个差灾区和 $c (x, y)$ 取最小值的结果
$F[y]=D[y]+\begin{cases} min\left(F[x]-min(D[y],c(x,y)),c(x,y)\right)& x的度数>1\\ c(x,y)&x的度数=1 \end{cases}$
$F [y]$ 就是把源点从 $x$ 换成 $y$ 后，流量的计算结果。

void dfs(int x)
{
    
    v[x]=1;
    for(int i=Link[x];i;i=a[i].Next)
    {
    
        int y=a[i].y;
        if(v[y])
        {
    
            continue ;
        }
        int v=a[i].v;
        if(deg[x]==1)
        {
    
            f[y]=d[y]+v;
        }
        else
        {
    
            f[y]=d[y]+min(f[x]-min(d[y],v),v);
        }
        dfs(y);
    }
}

最后的代码就不贴了，就是求出 $f$ 数组之后求个 $m a x$ 就完事了

本文链接：https://blog.csdn.net/weixin_44351585/article/details/101383777

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

hive使用适用场景_大数据入门：Hive应用场景-程序员宅基地

文章浏览阅读5.8k次。在大数据的发展当中，大数据技术生态的组件，也在不断地拓展开来，而其中的Hive组件，作为Hadoop的数据仓库工具，可以实现对Hadoop集群当中的大规模数据进行相应的数据处理。今天我们的大数据入门分享，就主要来讲讲，Hive应用场景。关于Hive，首先需要明确的一点就是，Hive并非数据库，Hive所提供的数据存储、查询和分析功能，本质上来说，并非传统数据库所提供的存储、查询、分析功能。Hive..._hive应用场景

zblog采集-织梦全自动采集插件-织梦免费采集插件_zblog 网页采集插件-程序员宅基地

文章浏览阅读496次。Zblog是由Zblog开发团队开发的一款小巧而强大的基于Asp和PHP平台的开源程序，但是插件市场上的Zblog采集插件，没有一款能打的，要么就是没有SEO文章内容处理，要么就是功能单一。很少有适合SEO站长的Zblog采集。人们都知道Zblog采集接口都是对Zblog采集不熟悉的人做的，很多人采取模拟登陆的方法进行发布文章，也有很多人直接操作数据库发布文章，然而这些都或多或少的产生各种问题，发布速度慢、文章内容未经严格过滤，导致安全性问题、不能发Tag、不能自动创建分类等。但是使用Zblog采._zblog 网页采集插件

Flink学习四：提交Flink运行job_flink定时运行job-程序员宅基地

文章浏览阅读2.4k次，点赞2次，收藏2次。restUI页面提交1.1 添加上传jar包1.2 提交任务job1.3 查看提交的任务2. 命令行提交./flink-1.9.3/bin/flink run -c com.qu.wc.StreamWordCount -p 2 FlinkTutorial-1.0-SNAPSHOT.jar3. 命令行查看正在运行的job./flink-1.9.3/bin/flink list4. 命令行查看所有job./flink-1.9.3/bin/flink list --all._flink定时运行job

STM32-LED闪烁项目总结_嵌入式stm32闪烁led实验总结-程序员宅基地

文章浏览阅读1k次，点赞2次，收藏6次。这个项目是基于STM32的LED闪烁项目，主要目的是让学习者熟悉STM32的基本操作和编程方法。在这个项目中，我们将使用STM32作为控制器，通过对GPIO口的控制实现LED灯的闪烁。这个STM32 LED闪烁的项目是一个非常简单的入门项目，但它可以帮助学习者熟悉STM32的编程方法和GPIO口的使用。在这个项目中，我们通过对GPIO口的控制实现了LED灯的闪烁。LED闪烁是STM32入门课程的基础操作之一，它旨在教学生如何使用STM32开发板控制LED灯的闪烁。_嵌入式stm32闪烁led实验总结

Debezium安装部署和将服务托管到systemctl-程序员宅基地

文章浏览阅读63次。本文介绍了安装和部署Debezium的详细步骤，并演示了如何将Debezium服务托管到systemctl以进行方便的管理。本文将详细介绍如何安装和部署Debezium，并将其服务托管到systemctl。解压缩后，将得到一个名为"debezium"的目录，其中包含Debezium的二进制文件和其他必要的资源。注意替换"ExecStart"中的"/path/to/debezium"为实际的Debezium目录路径。接下来，需要下载Debezium的压缩包，并将其解压到所需的目录。

Android 控制屏幕唤醒常亮或熄灭_android实现拿起手机亮屏-程序员宅基地

文章浏览阅读4.4k次。需求：在诗词曲文项目中，诗词整篇朗读的时候，文章没有读完会因为屏幕熄灭停止朗读。要求：在文章没有朗读完毕之前屏幕常亮，读完以后屏幕常亮关闭；1.权限配置：设置电源管理的权限。

随便推点

目标检测简介-程序员宅基地

文章浏览阅读2.3k次。目标检测简介、评估标准、经典算法_目标检测

记SQL server安装后无法连接127.0.0.1解决方法_sqlserver 127 0 01 无法连接-程序员宅基地

文章浏览阅读6.3k次，点赞4次，收藏9次。实训时需要安装SQL server2008 R所以我上网上找了一个.exe 的安装包链接：https://pan.baidu.com/s/1_FkhB8XJy3Js_rFADhdtmA提取码：ztki注：解压后1.04G安装时Microsoft需下载.NET，更新安装后会自动安装如下：点击第一个傻瓜式安装，唯一注意的是在修改路径的时候如下不可修改：到安装实例的时候就可以修改啦数据..._sqlserver 127 0 01 无法连接

js 获取对象的所有key值，用来遍历_js 遍历对象的key-程序员宅基地

文章浏览阅读7.4k次。1. Object.keys(item); 获取到了key之后就可以遍历的时候直接使用这个进行遍历所有的key跟valuevar infoItem={ name:'xiaowu', age:'18',}//的出来的keys就是[name,age]var keys=Object.keys(infoItem);2. 通常用于以下实力中 <div *ngFor="let item of keys"> <div>{{item}}.._js 遍历对象的key

粒子群算法（PSO）求解路径规划_粒子群算法路径规划-程序员宅基地

文章浏览阅读2.2w次，点赞51次，收藏310次。粒子群算法求解路径规划路径规划问题描述给定环境信息，如果该环境内有障碍物，寻求起始点到目标点的最短路径，并且路径不能与障碍物相交，如图 1.1.1 所示。1.2 粒子群算法求解1.2.1 求解思路粒子群优化算法（PSO），粒子群中的每一个粒子都代表一个问题的可能解，通过粒子个体的简单行为，群体内的信息交互实现问题求解的智能性。在路径规划中，我们将每一条路径规划为一个粒子，每个粒子群群有 n 个粒子，即有 n 条路径，同时，每个粒子又有 m 个染色体，即中间过渡点的_粒子群算法路径规划

量化评价：稳健的业绩评价指标_rar 海龟-程序员宅基地

文章浏览阅读353次。所谓稳健的评估指标，是指在评估的过程中数据的轻微变化并不会显著的影响一个统计指标。而不稳健的评估指标则相反，在对交易系统进行回测时，参数值的轻微变化会带来不稳健指标的大幅变化。对于不稳健的评估指标，任何对数据有影响的因素都会对测试结果产生过大的影响，这很容易导致数据过拟合。_rar 海龟

IAP在ARM Cortex-M3微控制器实现原理_value line devices connectivity line devices-程序员宅基地

文章浏览阅读607次，点赞2次，收藏7次。–基于STM32F103ZET6的UART通讯实现一、什么是IAP，为什么要IAPIAP即为In Application Programming(在应用中编程)，一般情况下，以STM32F10x系列芯片为主控制器的设备在出厂时就已经使用J-Link仿真器将应用代码烧录了，如果在设备使用过程中需要进行应用代码的更换、升级等操作的话，则可能需要将设备返回原厂并拆解出来再使用J-Link重新烧录代码，这就增加了很多不必要的麻烦。站在用户的角度来说，就是能让用户自己来更换设备里边的代码程序而厂家这边只需要提供给_value line devices connectivity line devices