hdu 5176 The Experience of Love
2024-09-06 15:06:02
The Experience of Love
Accepts: 11
Submissions: 108
Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
一个叫Gorwin的女孩和一个叫Vivin的男孩是一对情侣。他们来到一个叫爱情的国家，这个国家由NN个城市组成而且只有N-1N−1条小道(像一棵树),每条小道有一个值表示两个城市间的距离。他们选择两个城市住下，Gorwin在一个城市Vivin在另外一个，第一次约会，Gorwin去找Vivin,她会写下路径上最长的一条小道(maxValue),第二次约会,Vivin去找Gorwin,他会写下路径上最短的一条小道(minValue),然后计算maxValue减去minValue的结果作为爱情经验值，再然后重新选择两个城市居住而且计算新的爱情经验值，重复一次又一次。 当他们选择过所有的情况后，请帮助他们计算一下爱情经验值的总和。
输入描述
大约有55组数据在输入文件。
对于每一组测试数据，第一行一个数NN,然后N-1N−1行，每行三个数aa, bb和cc，表示一条小道连接城市aa和城市bb,距离为cc. [参数说明]
1 < N <= 150000,1 <= a, b <= n,1 <= c <= {10}^{9}1<N<=150000,1<=a,b<=n,1<=c<=109
输出描述
每组测试数据输出一行，输出格式为 Case #x: answer, x表示数据编号,answer表示爱情经验值的总和。
输入样例
3
1 2 1
2 3 2
5
1 2 2
2 3 5
2 4 7
3 5 4
输出样例
Case #1: 1
Case #2: 17
Hint
请注意输入文件较大。 对于第一个样例：
最大值是1最小值是1，当他们选择城市1和2，爱情经验值是0.
最大值是2最小值是2，当他们选择城市2和3，爱情经验值是0.
最大值是2最小值是1，当他们选择城市1和3，爱情经验值是1.
所以爱情经验值的总和就是1。 对于边i，与u相连的点有m个，与v相连的边有n个，如果按权值从小到大排，那么每次都能求得从m个中的一个节点到n个中的一个节点路径的最大值，就是wi，因为之前所处理的所有边权值
都小于wi。反之求最小值也一样。
#include <iostream>
#include <algorithm>
#include <cstdio>
#define LL unsigned long long
using namespace std;
const int Max=+;
int f[Max],num[Max];
struct edge
{
int u,v,w;
}e[Max];
bool cmp1(edge a,edge b)
{
return a.w<b.w;
}
bool cmp2(edge a,edge b)
{
return a.w>b.w;
}
int find(int x)
{
return f[x]==-?x:f[x]=find(f[x]);
}
int main()
{
int n,ca=;
while(~scanf("%d",&n))
{
for(int i=;i<n;i++)
{
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
}
for(int i=;i<=n;i++) f[i]=-,num[i]=;
sort(e+,e+n,cmp1);
LL maxsum=,t=;
for(int i=;i<n;i++)
{
int pa=find(e[i].u);
int pb=find(e[i].v);
if(pa!=pb)
{
f[pa]=pb; //设pb为pa的父节点
maxsum+=t*num[pa]*num[pb]*e[i].w;
num[pb]+=num[pa]; //那么pa对到pb的节点个数和有所增益
}
}
sort(e+,e+n,cmp2);
LL minsum=;
for(int i=;i<=n;i++) f[i]=-,num[i]=;
for(int i=;i<n;i++)
{
int pa=find(e[i].u);
int pb=find(e[i].v);
if(pa!=pb)
{
f[pa]=pb;
minsum+=t*num[pa]*num[pb]*e[i].w;
num[pb]+=num[pa];
}
}
printf("Case #%d: %I64u\n",ca++,maxsum-minsum);
}
return ;
}
最新文章
- Atitit.如何建立研发体系
- 初次接触json...
- 导致VC不能释放的几个原因
- Java内部接口的调用方式
- Problem 2020 组合（FOJ)
- 操作系统：cpu调度 6-25
- window7资源管理器一直重启（百度知道找到可用）
- Python进阶04 函数的参数对应
- XXX项目 android 开发笔记
- HDU 5810 Balls and Boxes （找规律）
- Codeforces Gym 100338B Geometry Problem 计算几何
- 基于keepalived对redis做高可用配置---转载
- poj 3053 Fence Repair(优先队列)
- SQL Server多表同时查询
- sqlite效率探测
- 搞定导致CPU爆满的“罪魁祸首”
- 微信公众平台网页登录授权多次重定向跳转，导致code使用多次问题
- 『2019/4/9 TGDay2模拟赛 反思与总结』
- 我理解的vue生命周期
- Mybatis 传递多个参数