ybtoj【图论】2章4题【构造完全图】_构造从完全图kn的所有无圈定向到{1,2,...,n}上的排列之间的双射-程序员宅基地

构造完全图

题目

解析

开始推结论：
显然像拓扑排序一样，应当从边权从小到大考虑每条边才能保证无影响，即kruskal
然后考虑每条边加上时的贡献：多连了 $siz_x*siz_y$ 条边，边权都是 $d_i+1$ ，只有一个不是，很容易推出kruskal合并时的改变，其他就是板子

code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
int n,m,fa[100010],siz[100010],total=1;
struct f
{
    
	int x,y,z;
}a[100010];
bool cmp(f x,f y)
{
    
	return x.z<y.z;
}
int find(int d)
{
    
	if(fa[d]==d)return d;
	return fa[d]=find(fa[d]);
}
signed main()
{
    
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;
	for(int i=1;i<n;++i)scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);
	sort(a+1,a+n,cmp);
	for(int i=1;i<n;++i)
	{
    
		a[i].x=find(a[i].x),a[i].y=find(a[i].y);
		if(a[i].x!=a[i].y)
		{
    
			fa[a[i].x]=a[i].y;
			total+=(a[i].z+1)*siz[a[i].x]*siz[a[i].y];
			siz[a[i].y]+=siz[a[i].x];
		}
	}
	printf("%lld",total-n);
	return 0;
}

本文链接：https://blog.csdn.net/zhanglili1597895/article/details/117826292

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

智能推荐

基于UDS的CAN通信故障诊断_汽车故障诊断是利用ecu监测控制系统各组成部分的工作情况,发现故障后自动启动故障-程序员宅基地

文章浏览阅读9.6k次，点赞16次，收藏89次。摘要：阐述一种诊断控制单元之间通信丢失故障的机制，通过基于UDS的诊断协议进行原理分析，并制定一种有效的诊断处理策略。汽车故障诊断是利用ECU监测控制系统各组成部分的工作情况，发现故障后自动启动故障记录和处理逻辑。汽车故障诊断模块不仅能够存储记忆汽车故障，还能够实时提供汽车各种运行参数川。外部诊断设备通过一定的诊断通信规则与ECU建立诊断通信，并读取这些故障和参数，同时解析出来供外部测..._汽车故障诊断是利用ecu监测控制系统各组成部分的工作情况,发现故障后自动启动故障

JavaEE（三）:JSP_jsp用gbk servlet 用什么编码-程序员宅基地

文章浏览阅读387次。一、JSP简介 JSP（Java Server Pages）是JavaWeb服务器端的动态资源,它与html页面的作用是相同的，显示数据和获取数据。JSP其实是一种特殊的Servlet，当jsp页面第一次被访问时，服务器会把jsp编译成java文件。二、JSP页面组成静态内容HTML静态文本指令以“<%@”开始，以"%>"结束。比如：<%@include file="Fil..._jsp用gbk servlet 用什么编码

arcgis渔网分割提取栅格图_[GIS]网格化分析图绘制-程序员宅基地

文章浏览阅读2.5w次，点赞46次，收藏228次。网格化的目的是让各个数据更加标准化的进行统计。因各个网格位置受控，也有利于大量数据的对比与叠加计算。本文将示意如何完成一张标准的网格化分析图。一、会用到的软件ARCGIS二、创建格网2.1 制作流程确认边界 --> 创建渔网 --> 裁剪渔网2.2 确认边界这里以义乌市举例，添加义乌市市区SHP边界数据。全工程坐标系皆为WGS84。2.3 创建渔网 fishnet运行创建渔网..._分割栅格arcgis 输出基本名称

新建数据库_新建数据库怎么操作-程序员宅基地

文章浏览阅读1.1w次，点赞2次，收藏25次。注意看红色箭头，共有13个步骤，按顺序操作下去1、打开SQL Server2014的软件，然后点击连接服务器2、右键点击数据库3、数据库名称自定义4、最后点击确认注意：数据库名称不能为空5.刷新数据库6.然后就可以看到自己命名的的数据库了7.然后打开所需的数据表 8.注意一定要选择自己刚新建的表，不然会报错9.然后点击执行10.最后出现这些文字就代表执行成功注意刚把表引进来的时候会出现卡顿现象，只要随意点击一下就可以恢复了11.如果重..._新建数据库怎么操作

WinAPI编程入门笔记_declspec_import farproc winapi-程序员宅基地

文章浏览阅读1.4w次，点赞3次，收藏14次。今天写的这篇文章的主要意图就是给winAPI编程实践的一个小小的启发；因为winAPI编程时，我们用到很多的函数都是带有很多的参数，而且有时要进行相应的强制类型转换，所以熟悉常用的一些类型是非常重要的；（只有熟悉它们，我们才不会害怕!）现在好像没有一个好的,能很快速入门的方法，所以只能靠自己来琢磨了，呵呵！废话就说到这里，让我们进入主题吧！我们在api编程时经常会用到函数Message_declspec_import farproc winapi

Mybatis框架简介_简述mybatis框架组成。-程序员宅基地

文章浏览阅读230次。Mybatis框架简介_简述mybatis框架组成。

随便推点

ROS: Cannot mix incompatible Qt library (version 0x50905) with this library (version 0x50c01)-程序员宅基地

文章浏览阅读2.5k次，点赞3次，收藏3次。错误开始尝试使用rosrun turtlesim turtlesim_node运行ROS的入门样例时，出现这样的错误：Cannot mix incompatible Qt library (version 0x50905) with this library (version 0x50c01) Aborted (core dumped)根据提示可以判断是QT的版本不兼容导致的错误，百度知道查看当前QT版本：$ qmake -vQMake version 2.01aUsing Qt version _cannot mix incompatible qt library (version 0x50905) with this library (vers