P1955 [NOI2015] 程序自动分析 (并查集 + 离散化)
2021/4/16 22:26:09
本文主要是介绍P1955 [NOI2015] 程序自动分析 (并查集 + 离散化),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
程序自动分析
题目传送门
解题思路
先排序
把所有e=1的操作放在前面
然后再进行e=0的操作
在进行e=1的操作的时候
我们只要把它约束的两个变量放在同一个集合里面即可
在e=0,即存在一条不相等的约束条件,
于它约束的两个变量
如果在一个集合里面
那就不可能满足
如不相等的约束条件都满足
那就YES
数据太大,建议用离散化
离散化
AC代码
#include<algorithm> #include<cstdio> using namespace std; int tot,f[1000005],b[100005*3]; struct node { int x,y,z; }a[1000005]; bool cmp(node x,node y) { return x.z>y.z; } int find(int x) { if(f[x]==x)return x; return f[x]=find(f[x]); } int main() { int n,t; scanf("%d",&t); while(t--) { int ok=1; tot=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); b[++tot]=a[i].x; b[++tot]=a[i].y; } sort(b,b+tot); int m=unique(b,b+tot)-b;//去重 for(int i=1;i<=n;i++) { a[i].x=lower_bound(b,b+m,a[i].x)-b; a[i].y=lower_bound(b,b+m,a[i].y)-b; } for(int i=1;i<=m;i++)f[i]=i;//初值 sort(a+1,a+n+1,cmp);//排序 for(int i=1;i<=n;i++) { int xx=find(a[i].x),yy=find(a[i].y); if(a[i].z)f[xx]=yy; else if(xx==yy) { printf("NO\n"); ok=0; break; } } if(ok)printf("YES\n"); } return 0; }
谢谢
这篇关于P1955 [NOI2015] 程序自动分析 (并查集 + 离散化)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)