Codeforces Contest 1108 problem F MST Unification —— 构建唯一最小生成树

本文主要是介绍Codeforces Contest 1108 problem F MST Unification —— 构建唯一最小生成树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

You are given an undirected weighted connected graph with n vertices and m edges without loops and multiple edges.

The i-th edge is ei=(ui,vi,wi); the distance between vertices ui and vi along the edge ei is wi (1≤wi). The graph is connected, i. e. for any pair of vertices, there is at least one path between them consisting only of edges of the given graph.

A minimum spanning tree (MST) in case of positive weights is a subset of the edges of a connected weighted undirected graph that connects all the vertices together and has minimum total cost among all such subsets (total cost is the sum of costs of chosen edges).

You can modify the given graph. The only operation you can perform is the following: increase the weight of some edge by 1. You can increase the weight of each edge multiple (possibly, zero) times.

Suppose that the initial MST cost is k. Your problem is to increase weights of some edges with minimum possible number of operations in such a way that the cost of MST in the obtained graph remains k, but MST is unique (it means that there is only one way to choose MST in the obtained graph).

Your problem is to calculate the minimum number of operations required to do it.

Input
The first line of the input contains two integers n and m (1≤n≤2⋅105,n−1≤m≤2⋅105) — the number of vertices and the number of edges in the initial graph.

The next m lines contain three integers each. The i-th line contains the description of the i-th edge ei. It is denoted by three integers ui,vi and wi (1≤ui,vi≤n,ui≠vi,1≤w≤109), where ui and vi are vertices connected by the i-th edge and wi is the weight of this edge.

It is guaranteed that the given graph doesn’t contain loops and multiple edges (i.e. for each i from 1 to m ui≠vi and for each unordered pair of vertices (u,v) there is at most one edge connecting this pair of vertices). It is also guaranteed that the given graph is connected.

Output
Print one integer — the minimum number of operations to unify MST of the initial graph without changing the cost of MST.

Examples
inputCopy
8 10
1 2 1
2 3 2
2 4 5
1 4 2
6 3 3
6 1 3
3 5 2
3 7 1
4 8 1
6 2 4
outputCopy
1
inputCopy
4 3
2 1 3
4 3 4
2 4 1
outputCopy
0
inputCopy
3 3
1 2 1
2 3 2
1 3 3
outputCopy
0
inputCopy
3 3
1 2 1
2 3 3
1 3 3
outputCopy
1
inputCopy
1 0
outputCopy
0
inputCopy
5 6
1 2 2
2 3 1
4 5 3
2 4 2
1 4 2
1 5 3
outputCopy
2

题意:

给你一张图,让你增加某些边的值使得最小生成树唯一,输出增加的最小次数。

题解:

如果两个块合并的话,那么肯定是使得这两个块之间的边最小值只有一个,其他的最小值都改变,那么我们排序后每次只对相同的边长的边进行操作,如果这个边的两个点已经在一个并查集内,那么就说明这个边不需要考虑,因为有比他小的边了,之后在插的时候,如果这两个点不在同一个并查集内,就说明这两个块之前没有边相连,–,剩下的就是重复的边了。

#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>
const int N=2e5+5;
struct node
{int x,y,w;bool operator< (const node& a)const{return w<a.w;}
}e[N];
int fa[N];
int finds(int x)
{return x==fa[x]?fa[x]:fa[x]=finds(fa[x]);
}
int main()
{//memset(head,-1,sizeof(head));int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)fa[i]=i;int x,y,w;for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);sort(e+1,e+1+m);int ans=0,ne=0,fin=1;for(int i=1;i<=m;){while(fin<=m&&e[fin].w==e[i].w)fin++;int cnt=fin-i;for(int j=i;j<fin;j++)if(finds(e[j].x)==finds(e[j].y))cnt--;for(int j=i;j<fin;j++){if(finds(e[j].x)!=finds(e[j].y))cnt--;fa[finds(e[j].y)]=finds(e[j].x);}i=fin;ans+=cnt;}printf("%d\n",ans);return 0;
}

这篇关于Codeforces Contest 1108 problem F MST Unification —— 构建唯一最小生成树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

基于Python构建一个高效词汇表

《基于Python构建一个高效词汇表》在自然语言处理(NLP)领域,构建高效的词汇表是文本预处理的关键步骤,本文将解析一个使用Python实现的n-gram词频统计工具,感兴趣的可以了解下... 目录一、项目背景与目标1.1 技术需求1.2 核心技术栈二、核心代码解析2.1 数据处理函数2.2 数据处理流程

Python FastMCP构建MCP服务端与客户端的详细步骤

《PythonFastMCP构建MCP服务端与客户端的详细步骤》MCP(Multi-ClientProtocol)是一种用于构建可扩展服务的通信协议框架,本文将使用FastMCP搭建一个支持St... 目录简介环境准备服务端实现(server.py)客户端实现(client.py)运行效果扩展方向常见问题结

详解如何使用Python构建从数据到文档的自动化工作流

《详解如何使用Python构建从数据到文档的自动化工作流》这篇文章将通过真实工作场景拆解,为大家展示如何用Python构建自动化工作流,让工具代替人力完成这些数字苦力活,感兴趣的小伙伴可以跟随小编一起... 目录一、Excel处理:从数据搬运工到智能分析师二、PDF处理:文档工厂的智能生产线三、邮件自动化:

Python实现自动化Word文档样式复制与内容生成

《Python实现自动化Word文档样式复制与内容生成》在办公自动化领域,高效处理Word文档的样式和内容复制是一个常见需求,本文将展示如何利用Python的python-docx库实现... 目录一、为什么需要自动化 Word 文档处理二、核心功能实现:样式与表格的深度复制1. 表格复制(含样式与内容)2

python如何生成指定文件大小

《python如何生成指定文件大小》:本文主要介绍python如何生成指定文件大小的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录python生成指定文件大小方法一(速度最快)方法二(中等速度)方法三(生成可读文本文件–较慢)方法四(使用内存映射高效生成

详解如何使用Python从零开始构建文本统计模型

《详解如何使用Python从零开始构建文本统计模型》在自然语言处理领域,词汇表构建是文本预处理的关键环节,本文通过Python代码实践,演示如何从原始文本中提取多尺度特征,并通过动态调整机制构建更精确... 目录一、项目背景与核心思想二、核心代码解析1. 数据加载与预处理2. 多尺度字符统计3. 统计结果可

Maven项目中集成数据库文档生成工具的操作步骤

《Maven项目中集成数据库文档生成工具的操作步骤》在Maven项目中,可以通过集成数据库文档生成工具来自动生成数据库文档,本文为大家整理了使用screw-maven-plugin(推荐)的完... 目录1. 添加插件配置到 pom.XML2. 配置数据库信息3. 执行生成命令4. 高级配置选项5. 注意事

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2

一文教你Java如何快速构建项目骨架

《一文教你Java如何快速构建项目骨架》在Java项目开发过程中,构建项目骨架是一项繁琐但又基础重要的工作,Java领域有许多代码生成工具可以帮助我们快速完成这一任务,下面就跟随小编一起来了解下... 目录一、代码生成工具概述常用 Java 代码生成工具简介代码生成工具的优势二、使用 MyBATis Gen

Python使用Reflex构建现代Web应用的完全指南

《Python使用Reflex构建现代Web应用的完全指南》这篇文章为大家深入介绍了Reflex框架的设计理念,技术特性,项目结构,核心API,实际开发流程以及与其他框架的对比和部署建议,感兴趣的小伙... 目录什么是 ReFlex?为什么选择 Reflex?安装与环境配置构建你的第一个应用核心概念解析组件