Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


小Y的问题

题目描述

有个孩子叫小 Y,一天,小 Y 拿到了一个包含 n 个点和 n-1 条边的无向连通图, 图中的点用 1~n 的整数编号。小 Y 突发奇想,想要数出图中有多少个“Y 字形”。

一个“Y 字形”由 5 个不同的顶点 A、 B、 C、 D、 E 以及它们之间的 4 条边组成,其中 AB、BC、 BD、 DE 之间有边相连, 如下图所示。
Markdown
同时,无向图中的每条边都是有一定长度的。一个“Y 字形”的长度定义为构成它的四条边的长度和。小 Y也想知道,图中长度最大的“Y 字形”长度是多少。


输入格式

第一行包含一个整数 n,表示无向图的点数。

接下来 n 行, 每行有 3 个整数 x、 y、 z, 表示编号为 x 和 y 的点之间有一条长度为 z 的边。


输出格式

输出包含 2 行。

第 1 行包含一个整数,表示图中的“Y 字形”的数量。

第 2 行包含一个整数,表示图中长度最大的“Y 字形”的长度。

解题思路

预处理与每个点相连的边数(度数),每个点连的边的边权的最大值,次大值,第三大值
枚举Y字形中间那条边B-D
利用B和D的度数,用乘法原理计算出以B-D为中心的Y字形数量
利用预处理的结果,O(1)求出与B相连的边中除了B-D以外边权的最大值,次大值,求出与D相连的边中除了B-D以外边权的最大值


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
#define M 200005
using namespace std;
struct Node{
int to,w;
bool operator <(const Node &a)const{
return w>a.w;
}
};
vector<Node>G[M];
int main(){
freopen("question.in","r",stdin);
freopen("question.out","w",stdout);
int n,maxans=0;
scanf("%d",&n);
ll ans=0;
for(int i=1;i<n;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
G[a].push_back((Node){b,c});
G[b].push_back((Node){a,c});
}
for(int i=1;i<=n;i++){
int cnt=0;
if(G[i].size()<3)continue;
for(int j=0;j<G[i].size();j++)
if(G[G[i][j].to].size()>1)cnt+=G[G[i][j].to].size()-1;
ans+=1LL*cnt*(G[i].size()-1)*(G[i].size()-2)/2;
}
cout<<ans<<endl;
for(int i=1;i<=n;i++)
sort(G[i].begin(),G[i].end());
for(int i=1;i<=n;i++){
if(G[i].size()<3)continue;
for(int j=0;j<G[i].size();j++){
int to=G[i][j].to,res=0;
if(G[to].size()==1)continue;
if(to==G[i][0].to)res=G[i][1].w+G[i][2].w;
else if(to==G[i][1].to)res=G[i][0].w+G[i][2].w;
else res=G[i][0].w+G[i][1].w;
int d;
if(G[to][0].to==i)d=G[to][1].w;
else d=G[to][0].w;
if(res+d+G[i][j].w>maxans)maxans=res+d+G[i][j].w;
}
}
printf("%d\n",maxans);
return 0;
}

Markdown

最近的文章

矩阵快速幂

于 继续阅读
更早的文章

铺瓷砖

题目描述 有一面很长很长的墙。 你需要在这面墙上贴上两行瓷砖。 你的手头有两种不同尺寸的瓷砖, 你希望用这两种瓷砖各贴一行。瓷砖的长可以用分数表示,贴在第一行的每块瓷砖长度为A/B,贴在第二行的每块瓷砖长度为C/D。 本问题中你并不需要关心瓷砖的宽度。如上图所示, 两排瓷砖从同一起始位置开始向右排列 …

于  gcd 继续阅读