- 题解
加边入树判定
- @ 2026-8-3 18:26:12
#include<bits/stdc++.h>
using namespace std;
int p[200001];
int find(int x) {
if(p[x]==x) return x;
return p[x]=find(p[x]);
}
struct node {
int u,v,w;
} a[200001];
struct ne {
int u,v,w,pos;
} b[200001];
bool cmp1(node x,node y) {
return x.w<y.w;
}
bool cmp2(ne x,ne y) {
return x.w<y.w;
}
bool ans[200001];
int main() {
int n,m,q;
cin >> n >> m >> q;
for(int i=1; i<=n; i++) {
p[i]=i;
}
for(int i=1; i<=m; i++) {
cin >> a[i].u >> a[i].v >> a[i].w;
}
for(int i=1; i<=q; i++) {
cin >> b[i].u >> b[i].v >> b[i].w;
b[i].pos=i;
}
sort(a+1,a+m+1,cmp1);
sort(b+1,b+q+1,cmp2);
int po=1;
int cnt=0;
for(int i=1; i<=m&&po<=q&&cnt<n-1; i++) {
while(a[i].w>b[po].w&&po<=q) {
int pu=find(b[po].u),pv=find(b[po].v);
if(pu==pv) ans[b[po].pos]=false;
else ans[b[po].pos]=true;
po++;
}
int pu=find(a[i].u),pv=find(a[i].v);
if(pu!=pv) {
cnt++;
p[pu]=pv;
}
}
if(po!=q+1) {
for(int i=po; i<=q; i++) {
ans[b[i].pos]=false;
}
}
for(int i=1; i<=q; i++) {
if(ans[i]) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
0 条评论
目前还没有评论...