积累程度 poj3585

2024-09-04 23:18
文章标签 积累 程度 poj3585

本文主要是介绍积累程度 poj3585,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

有一个树形的水系,由 N-1 条河道和 N 个交叉点组成。

我们可以把交叉点看作树中的节点,编号为 1~N,河道则看作树中的无向边。

每条河道都有一个容量,连接 x 与 y 的河道的容量记为 c(x,y)。

河道中单位时间流过的水量不能超过河道的容量。

有一个节点是整个水系的发源地,可以源源不断地流出水,我们称之为源点。

除了源点之外,树中所有度数为 1 的节点都是入海口,可以吸收无限多的水,我们称之为汇点。

也就是说,水系中的水从源点出发,沿着每条河道,最终流向各个汇点。

在整个水系稳定时,每条河道中的水都以单位时间固定的水量流向固定的方向。

除源点和汇点之外,其余各点不贮存水,也就是流入该点的河道水量之和等于从该点流出的河道水量之和。

整个水系的流量就定义为源点单位时间发出的水量。

在流量不超过河道容量的前提下,求哪个点作为源点时,整个水系的流量最大,输出这个最大值。

输入格式

输入第一行包含整数T,表示共有T组测试数据。

每组测试数据,第一行包含整数N。

接下来N-1行,每行包含三个整数x,y,z,表示x,y之间存在河道,且河道容量为z。

节点编号从1开始。

输出格式

每组数据输出一个结果,每个结果占一行。

数据保证结果不超过231−1231−1。

数据范围

N≤2∗105N≤2∗105

输入样例:

1
5
1 2 11
1 4 13
3 4 5
4 5 10

输出样例:

26

最重要的数组要开大我开3e+测试的时候超时卡了一上午没看出来(忘了考虑存的是无向图),我想应该是数组模拟的邻接表在存数据的时候计数变量超了,如果是用结构体的话应该就可以开2e+。 这就是 二次扫描+换根法的典型题。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
typedef long long ll;using namespace std;
const int N=700100;
ll Head[N],edge[N],Next[N],dp[N],d[N],tot=0,point[N],du[N];
int n;
bool v[N];
inline void adds(int x,int y,int z)
{tot++;point[tot]=y;Next[tot]=Head[x];Head[x]=tot;edge[tot]=z;
}void dfsd(int x)
{v[x]=1;d[x]=0;for(int i=Head[x]; i; i=Next[i]){int y=point[i];if(v[y])continue;dfsd(y);if(du[y]==1)d[x]+=edge[i];elsed[x]+=min(edge[i],d[y]);}
}void dfs(int x)
{v[x]=1;for(int i=Head[x]; i; i=Next[i]){int y=point[i];if(v[y])continue;if(du[x]==1)dp[y]=edge[i]+d[y];else{dp[y]=d[y]+min(dp[x]-min(d[y],edge[i]),edge[i]);}dfs(y);}
}int main()
{int jb;scanf("%d",&jb);while(jb--){tot=0;memset(Next,0,sizeof(Next));memset(Head,0,sizeof(Head));memset(du,0,sizeof(du));cin>>n;for(int i=1; i<n; i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);adds(x,y,z);adds(y,x,z);du[x]++,du[y]++;}int root=1;memset(v,0,sizeof(v));dfsd(root);dp[root]=d[root];memset(v,0,sizeof(v));dfs(root);ll ans=-1;for(int i=1; i<=n; i++){ans=max(ans,dp[i]);//cout<<dp[i]<<' '<<d[i]<<endl;}printf("%lld\n",ans);}
}

 

这篇关于积累程度 poj3585的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137316

相关文章

js积累四

原型对象:        在创建一个新函数的时候,会根据一组特定规则为该函数创建一个prototype属性,这个属性指向函数的原型对象。        原型对象会自动获得一个constructor(构造函数)属性,这个属性包含一个指向prototype属性的在函数的指针。比如有一个构造函数:          function Persion(name,age){

js积累二

三,js里的参数(arguments对象) 当我们在调用一个函数时,在函数体内可以通过arguments对象来访问这个参数数组,从而获取传递给函数的每一个参数。 进一步说一下arguments对象:它只是与数组类似,并不是Array的实例,访问对象的属性值时可以使用方括号[]。 1,根据传入的参数个数arguments.length我们可以让同一个方法执行不同的任务: function te

js积累一

一、typeof操作符 检测js里给定变量的数据类型--typeof ECMAScript中有5种简单数据类型(也称基本数据类型):Undefined,Null,Boolean,Number和String 还有一种复杂数据类型:Object,其本质是由一组无序的名值对组成 对一个值使用typeof可能会返回如下某个字符串: "undefined" --- 如果这个值未定义 "boolean" -

解决乱码的积累

项目中调了外部的一个接口,返回的是xml格式,编码是GBK,项目中开发工具编码使用的是UTF-8,使用流来读取信息时用到了这个: InputStreamReader read = new InputStreamReader(new FileInputStream(f)); 因为在构造读取流时没有指定编码,所以出现了乱码,因此在实际使用过程中需要进行编码的指定。   返回的信息使用的是GBK,

绘制PCB经验积累

绘制板子层数究竟是通过什么来进行判断的? 1.电路的复杂程度 信号数量和密度,电源和地的分布要求 2.工作频率和信号速度   对于高速信号的定义,之前的文章有讲过,当信号的时钟频率超过5MHz,或信号上升/下降的时间小于5ns时,一般需要使用多层板的设计。原因在于多层板设计可以有效控制信号回路的面积,以此来获得优秀的电气性能。 3.空间限制和尺寸要求 小型化,元器件布局和散热考虑 .

讨论运维监控工具的普及程度

在讨论运维监控工具的普及程度时,加入PIGOSS BSM产品的分析是非常有意义的,因为PIGOSS BSM是一款在中国市场具有一定影响力的运维监控工具。 PIGOSS BSM运维监控工具是一款综合性的IT运维监控解决方案,它能够对多层次的IT资源进行监测,包括但不限于性能监测、事件管理、报表管理等功能模块。PIGOSS BSM的一个独特之处在于其拓扑关联配置工具,这使得用户可以根据自身的I

GAMES202——作业5 实时光线追踪降噪(联合双边滤波、多帧的投影与积累、À-Trous Wavelet 加速单帧降噪)

任务         1.实现单帧降噪         2.实现多帧投影         3.实现多帧累积         Bonus:使用À-Trous Wavelet 加速单帧降噪 实现         单帧降噪         这里实现比较简单,直接根据给出的联合双边滤波核的公式就能实现          Buffer2D<Float3> Denoiser::Fil

【科研积累】机器学习的认知笔记

一、机器学习通识 机器学习,就是用模型来学习数据的规律。 大多数机器学习任务都是三步走:实例化➡️训练➡️预测。 机器学习任务按照最后一步预测,可以分为三种: 1. 分类:输出概率分布 2. 回归 3. 生成:本质上也是分类,生成的是对下一个字的分类,在字典中,每个字都是一个类别。 如果按照数据标签的完整与否来划分,则可以分为以下三类: 1. 结构化的数据(全都有标签):用于监

【Oracle点滴积累】Oracle 19c安装Critical Patch Update for January 2024

广告位招租! 知识无价,人有情,无偿分享知识,希望本条信息对你有用! 今天和大家分享如何为Oracle 19c(未启用RMAN的单实例)安装Critical Patch Update(Patch Number:35943157),本指引不包含Roll Back部分,本文仅供参考,谢谢! cd /home/oracle/NewVersion_Opatch/OPatch/./opatch v

【Oracle点滴积累】解决IMP-00017、ORA-20005、ORA-06512错误的方法

广告位招租! 知识无价,人有情,无偿分享知识,希望本条信息对你有用! 今天和大家分享 IMP-00017: folloging statement failed with ORACLE error 20005 ORA-20005: object statistics are locked (stattype = ALL) 错误的解决方法,本文仅供参考,谢谢! select 'exec