NOIP2023模拟2联测23 害怕

2023-10-25 19:01
文章标签 模拟 23 联测 害怕 noip2023

本文主要是介绍NOIP2023模拟2联测23 害怕,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目大意

有一个有 n n n个点 m m m条边的无向图,每条边都有蓝白两种颜色中的一种,保证蓝色的边形成了这个图的一个生成树。

你要给这些边赋上边权,要求边权是 1 ∼ m 1\sim m 1m的序列,使得蓝色的边是最小生成树。

你希望这些边权形成的序列字典序最小,也就是先比较第一条边的边权,再比较第二条边的边权,依次类推。

1 ≤ n , m ≤ 5 × 1 0 5 , m ≥ n − 1 1\leq n,m\leq 5\times 10^5,m\geq n-1 1n,m5×105,mn1


题解

一个图的一棵树是最小生成树,当且仅当任意的非树边的边权都比与其形成环的树边大。

要让字典序最小,也就是要在蓝边形成最小生成树的前提下,让编号小的边尽量小。

我们按编号从小到大枚举边:

  • 如果是树边,且该边没有被赋值,则直接将其赋值
  • 如果是非树边,则将与其形成环的树边按编号从小到大赋值,再给这条非树边赋值

求与非树边形成环的树边,其实就是求非树边的两个点在树边上的路径。那么, 给与非树边形成环的树边其实就是在树上一边求 l c a lca lca一边给边赋值。

注意赋值是从小到大赋值,这样才能保证字典序最小。

在赋值的时候,每赋值完一条树边,我们可以用并查集来将树边上的两个点并起来,每次向上跳时只要到当前所在的并查集的编号最小的点,然后给这个点到父亲的边赋值即可。

但是,这样的话,它们有可能跳到 l c a lca lca上面的点。但这其实不影响,因为当两个点跳到同一个位置时就不会再跳了(也就是第一次跳到 l c a lca lca l c a lca lca的祖先时就不会再跳了),所以就不会对 l c a lca lca上面的边赋值。

因为用了并查集,所以我们可以暴力跳,每条边最多只会被跳一次,时间复杂度平摊下来是 O ( n ) O(n) O(n)的。在将树边按编号从小到大赋值时要对树边排序,总时间复杂度是 O ( n log ⁡ n ) O(n\log n) O(nlogn)的。

所以,总时间复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)

code

#include<bits/stdc++.h>
using namespace std;
const int N=500000;
int n,m,now=0,tot=0,d[2*N+5],l[2*N+5],r[N+5],id[2*N+5];
int fa[N+5],dep[N+5],tf[N+5],dn[N+5],up[N+5],ans[N+5];
struct node{int x,y,z;
}w[N+5];
void add(int xx,int yy,int i){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;id[tot]=i;
}
void dfs(int u,int f){fa[u]=f;dep[u]=dep[f]+1;tf[u]=u;for(int i=r[u];i;i=l[i]){if(d[i]==f) continue;dn[id[i]]=d[i];up[d[i]]=id[i];dfs(d[i],u);}
}
int find(int ff){if(ff!=tf[ff]) tf[ff]=find(tf[ff]);return tf[ff];
}
void pt(int x,int y){vector<int>v;x=find(x);y=find(y);while(x!=y){if(dep[x]<dep[y]) swap(x,y);v.push_back(up[x]);tf[x]=find(fa[x]);x=tf[x];}sort(v.begin(),v.end());for(int i=0;i<v.size();i++){ans[v[i]]=++now;}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1,x,y,z;i<=m;i++){scanf("%d%d%d",&x,&y,&z);w[i]=(node){x,y,z};if(z){add(x,y,i);add(y,x,i);}}dfs(1,0);for(int i=1;i<=m;i++){if(w[i].z){if(tf[dn[i]]==dn[i]){ans[i]=++now;tf[dn[i]]=find(fa[dn[i]]);}}else{pt(w[i].x,w[i].y);ans[i]=++now;}}for(int i=1;i<=m;i++){printf("%d ",ans[i]);}return 0;
}

这篇关于NOIP2023模拟2联测23 害怕的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

安卓链接正常显示,ios#符被转义%23导致链接访问404

原因分析: url中含有特殊字符 中文未编码 都有可能导致URL转换失败,所以需要对url编码处理  如下: guard let allowUrl = webUrl.addingPercentEncoding(withAllowedCharacters: .urlQueryAllowed) else {return} 后面发现当url中有#号时,会被误伤转义为%23,导致链接无法访问

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

【算法专场】模拟(下)

目录 前言 38. 外观数列 算法分析 算法思路 算法代码 1419. 数青蛙 算法分析 算法思路 算法代码  2671. 频率跟踪器 算法分析 算法思路 算法代码 前言 在前面我们已经讲解了什么是模拟算法,这篇主要是讲解在leetcode上遇到的一些模拟题目~ 38. 外观数列 算法分析 这道题其实就是要将连续且相同的字符替换成字符重复的次数+

模拟实现vector中的常见接口

insert void insert(iterator pos, const T& x){if (_finish == _endofstorage){int n = pos - _start;size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;reserve(newcapacity);pos = _start + n;//防止迭代

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

1 模拟——67. 二进制求和

1 模拟 67. 二进制求和 给你两个二进制字符串 a 和 b ,以二进制字符串的形式返回它们的和。 示例 1:输入:a = "11", b = "1"输出:"100"示例 2:输入:a = "1010", b = "1011"输出:"10101" 算法设计 可以从低位到高位(从后向前)计算,用一个变量carry记录进位,如果有字符没处理完或者有进位,则循环处理。两个字符串对