Codeforces891C. Envy
2024-09-04 20:17:20
$n \leq 5e5$,$m \leq 5e5$的无向边权图,$q \leq 5e5$个询问,每次问一系列边是否能同时存在于某棵最小生成树上。
一条边在最小生成树上,当比他小的边都加入后,加入他会使连通块数-1,也就是他两端的点在加入比他小的所有边后仍不在一起。
于是乎把所有询问的所有边排序,每次处理一个询问的一种边,新开一个并查集看看把这个询问的边加进去之后会不会有一条边是废的(没使连通块数-1,也就是两端点的并查集父亲相同)。
//#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
//#include<queue>
//#include<time.h>
//#include<complex>
#include<algorithm>
#include<stdlib.h>
using namespace std; int n,m,lq;
#define maxn 500011
struct Edge{int from,to,v;}edge[maxn];
int ufs[maxn],vis[maxn],ufsb[maxn];
int find(int x) {return ufs[x]==x?x:(ufs[x]=find(ufs[x]));}
int findb(int Time,int x) {return vis[x]==Time?(ufsb[x]==x?x:(ufsb[x]=findb(Time,ufsb[x]))):(vis[x]=Time,(ufsb[x]=find(x)));} bool ans[maxn];
struct vnode{int id,e;};
vector<vnode> v[maxn],ve[maxn]; int main()
{
scanf("%d%d",&n,&m); int maxv=;
for (int i=,x,y,val;i<=m;i++) scanf("%d%d%d",&x,&y,&val),maxv=max(maxv,val),
edge[i]=(Edge){x,y,val},ve[val].push_back((vnode){x,y}); scanf("%d",&lq);
for (int i=,x,y;i<=lq;i++)
{
scanf("%d",&x);
while (x--) scanf("%d",&y),v[edge[y].v].push_back((vnode){i,y});
} for (int i=;i<=n;i++) ufs[i]=i;
int Time=;
for (int i=;i<=maxv;i++)
{
for (int j=,last=,to=v[i].size();j<to;j++)
{
int id=v[i][j].id,x=edge[v[i][j].e].from,y=edge[v[i][j].e].to;
if (last!=id) ++Time;
if (vis[x]!=Time) vis[x]=Time,ufsb[x]=find(x);
if (vis[y]!=Time) vis[y]=Time,ufsb[y]=find(y);
if (findb(Time,x)==findb(Time,y)) ans[id]=;
ufsb[ufsb[x]]=ufsb[y];
last=id;
}
for (int j=,to=ve[i].size();j<to;j++)
{
int x=find(ve[i][j].id),y=find(ve[i][j].e);
if (x!=y) ufs[x]=y;
}
}
for (int i=;i<=lq;i++) puts(ans[i]?"NO":"YES");
return ;
}
最新文章
- JSP学习笔记
- [JS]笔记11之正则表达式
- MIT 6.824 : Spring 2015 lab3 训练笔记
- Linux内核学习之道
- 浮点与整形在GUI下的相关思考
- Android_Service组件详解
- 公钥password学中的素数以及对称加密
- class path resource [config.xml] cannot be opened because it does not exist
- Kubernetes日志收集
- Android Framework 学习和需要学习的内容
- 【Python3爬虫】你会怎么评价复仇者联盟4?
- 启动VMware虚拟机时总是出现许可证到期提示怎么办?
- kafka-producer配置
- POJ 1679 The Unique MST 【判断最小生成树是否唯一】
- JAVA基础知识总结:十二
- [日常] Go语言圣经-文本和HTML模板习题
- 通过ajax记录打印信息
- Retrofit2使用初探
- class kind type sort区别
- SQL Server 数据库优化剖析
热门文章
- BC div2补题以及 复习模除 逆元__BestCoder Round #78 (div.2)
- caffe修改需要的东西 6:40
- 【转】IntelliJ 创建main函数快捷
- MySQL 资料库概论与MySQL 安装
- Python可变与不可变类型及垃圾回收机制
- Errors occurred during the build. Errors running builder 'JavaScript Validator'
- Java-获取堆的大小
- luogu3759 [TJOI2017]不勤劳的图书管理员
- 大数据学习——Kafka集群部署
- C++类指针初始化