tyvj————小Y的问题

【问题描述】
有个孩子叫小 Y，一天，小 Y 拿到了一个包含 n 个点和 n-1 条边的无向连通图，图中的
点用 1~n 的整数编号。小 Y 突发奇想，想要数出图中有多少个“Y 字形”。
一个“Y 字形”由 5 个不同的顶点 A、B、C、D、E 以及它们之间的 4 条边组成，其中 AB、
BC、BD、DE 之间有边相连，如下图所示。
tyvj————小Y的问题
同时，无向图中的每条边都是有一定长度的。一个“Y 字形”的长度定义为构成它的四条
边的长度和。小 Y 也想知道，图中长度最大的“Y 字形”长度是多少。
【输入】
第一行包含一个整数 n，表示无向图的点数。
接下来 n 行，每行有 3 个整数 x、y、z，表示编号为 x 和 y 的点之间有一条长度为 z 的
边。
【输出】
输出包含 2 行。
第 1 行包含一个整数，表示图中的“Y 字形”的数量。
第 2 行包含一个整数，表示图中长度最大的“Y 字形”的长度。
【输入输出样例】
question.in

question.out

5
9

输入输出样例 1 说明】
图中共有 5 个“Y 字形”，如图中用红色标出的部分所示。
tyvj————小Y的问题
其中，长度最大的“Y 字形”是编号 3、5、7、4、6 的顶点构成的那一个，长度为 9。
【数据规模与约定】
对于 30%的数据，n≤10
对于 60%的数据，n≤2,000
对于 100%的数据，n≤200,000，1≤x,y≤n，1≤z≤10,000

解析与吐槽

对于这道题一开始我是懵逼的，试图打暴力WA，TLE。。。。。。
然后去看了讲解，~~果然自己还是个辣鸡~~ ，于是决定按照讲解写一个题解
下面是正文：
首先看数据规模，n≤200,000，对于这种规模时间复杂度无非两种： O(N) 或 O(NlogN)，我用的是O(N)的；
这样的话我们一次只能去枚举一个量，所以我们枚举Y字中间的那条边，也就是第一个图中的 B—D边（B假设为分叉点），此时对于B我们要求它的度数要求>=3,D要求度数>=2（不然你凭什么去组成"Y"），枚举量解决了，再来看题：
1·关于数量
如果我们假设B共a条边，D共b条边，我们每次拿出B的两条边和D的一条边去与B—D组成“Y”
容易得B和D的情况分别有（B的是组合数，不会的可以看人教版数学选修2—3，当然你也可以上网搜）：
tyvj————小Y的问题
所以我们每枚举一条边就将总数加上上面两个数的乘积，这样就处理完了数量；
注意：由于数据规模的锅，正解必须用long long
2·关于最大值
我们想使边权和最大，那么按照贪心的思想，我们可以每次枚举时除被枚举边B—D外，使剩余三条边都最大，但这时候我们不可能再枚举一边去求最大值（~~除非你想TLE~~ ），
所以我们就不得不使用一种强大的技巧————预处理，在读入时就求出每个点周围的最大，次大和第三大边（因为这时候我们枚举的边可能是最大或次大，这时候就会用上第三大）,然后枚举边时直接加起来，再和目前的最大值比较就OK了
最后，一点要注意当我们在存邻接表的时候，邻接表数组要开数据规模的2倍（因为是无向图啊），再顺带一提，由于读入可能太大，所以最好用一下scanf或读入优化（反正我用cin的同学都TLE了。。。。）

附上代码

（因为是一点点改的所以可能会有某些毛病）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL; 
const int MAXN=200005;
LL n,max_len=-1;
LL cnt;
LL max1[MAXN],max2[MAXN],max3[MAXN],num[MAXN];
LL h[MAXN*2],nxt[MAXN*2],to[MAXN*2],dis[MAXN*2],num_egde;
inline void add_sth(LL x,LL y,LL l)
{
	nxt[++num_egde]=h[x];
	to[num_egde]=y;
	dis[num_egde]=l;
	h[x]=num_egde;
	num[x]++;
	if(max1[x]<=l) {
		max3[x]=max2[x];max2[x]=max1[x];max1[x]=l;
	}
	else if(max2[x]<=l){
		max3[x]=max2[x];max2[x]=l;
	}
	else if(max3[x]<l)  max3[x]=l;
}
inline void work(LL x,LL y,LL w)
{
	LL sum=w;
	LL x1,y1;
	x1=(long long)(num[x]-1)*(num[x]-2)/2;
	y1=(long long)(num[y]-1);
	cnt+=x1*y1;
	if(w==max1[x]) 
	{
		if(w==max1[y]) sum=sum+max2[x]+max3[x]+max2[y];
		  else sum=sum+max2[x]+max3[x]+max1[y];
	}
	 else if(w==max2[x]) 
	 {
	 	if(w==max1[y]) sum=sum+max1[x]+max3[x]+max2[y];
	 	  else  sum=sum+max1[x]+max3[x]+max1[y];
	 }
	  else if(w<=max3[x]) 
	  {
	  	if(w==max1[y]) sum=sum+max1[x]+max2[x]+max2[y];
	  	  else sum=sum+max1[x]+max2[x]+max1[y];
	  }
	max_len=max(max_len,sum);
}
int main()
{
	LL u,v,w;
	scanf("%lld",&n);
	for(LL i=1;i<=n-1;i++)
	{
	  scanf("%lld%lld%lld",&u,&v,&w);
	  add_sth(u,v,w);
	  add_sth(v,u,w);
	} 
	for(LL i=1;i<=n;i++)
	  if(num[i]>=3)
	    for(LL j=h[i];j;j=nxt[j])
	      if(num[to[j]]>=2) work(i,to[j],dis[j]);
	printf("%lld\n",cnt);
	printf("%lld\n",max_len);
	return 0;
}

tyvj————小Y的问题

解析与吐槽

附上代码

相关推荐