程序自动分析 acw237
2022/6/11 1:21:34
本文主要是介绍程序自动分析 acw237,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
这题我没看见数据范围,就直接写了,其实思路差不多,把所有相等的放在一个集合里面,然后看看不等的,在不在同一个集合里面,在就是no,不在就是yes
但是这个数据范围是1e9,直接做空间不够用,但是n就是数的总个数才2e5个,所以可以想到离散化,离散化有两种:保序和不保序的,保序的看看基础课吧,我忘记了QAQ
不保序的就是把这些数对应到一个属于它们的编号,就可以了,按照编号来对应数字,我喜欢QAQ
还有要用scanf555,cin被卡了
详细看代码:
#include<iostream> #include<cstdio> #include<map> using namespace std; const int N=2e6+10; struct mess{ int x,y,e; }a[N]; int n; int p[N]; map<int,int> mp;//对应着某个数的编号 int get(int x) { if(!mp[x]) { n++; mp[x]=n; } return mp[x]; } int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main(){ int T; scanf("%d",&T); while(T--) { n=0; mp.clear(); int m; scanf("%d",&m); for(int i=0;i<m;i++) { int x,y,e; scanf("%d%d%d",&x,&y,&e); a[i]={get(x),get(y),e};//一一映射到代表这个数的编号并且存在结构体里面 } for(int i=1;i<=n;i++) p[i]=i; for(int i=0;i<m;i++) { if(a[i].e) { int xx=find(a[i].x),yy=find(a[i].y); p[xx]=yy; } } int f=1; for(int i=0;i<m;i++) { if(!a[i].e) { if(find(a[i].x)==find(a[i].y)) { f=0; break; } } } if(f) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
这篇关于程序自动分析 acw237的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升