数据太大,因此肯定要离散化。
考虑把e1的判断先全部放在前面,然后再考虑e0的部分。这么做的正确性是显然的,假设问题成立,则顺序无影响,假设问题不成里,矛盾也不会因为顺序改变而消失。
其实也可以按照原顺序考虑。只不过需要加入一个vis数组,标记每一个值是否被加入过判断条件。
写法如下
for(int i=1;i<=n;++i) { if(c[i]==1) { f(!vis[a[i]] || !vis[b[i]]) { Merge(a[i],b[i]); vis[a[i]]=true; vis[b[i]]=true; } else { int xx=Find(a[i]),yy=Find(b[i]); if(xx!=yy) { printf("NO\n"); flag=1; break; } } } else { if(!vis[a[i]] || !vis[b[i]]) { vis[a[i]]=true; vis[b[i]]=true; } else { int xx=Find(a[i]),yy=Find(b[i]); if(xx==yy) { printf("NO\n"); flag=1; break; } } } } if(!flag) printf("YES\n");
完整代码
Code
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+5000; int t,n,fa[maxn]; int book[maxn],flag=0; struct mint { int x,y,e; }a[maxn]; bool cmp(mint x,mint y) { return x.e > y.e; } int Find(int x) { if(fa[x]==x) return x; return fa[x]=Find(fa[x]); } void Merge(int x,int y) { int xx=Find(x),yy=Find(y); fa[xx]=yy; } int main() { scanf("%d",&t); for(int q=1;q<=t;++q) { flag=0; int tot=-1; memset(a,0,sizeof(a)); scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].e); book[++tot]=a[i].x; book[++tot]=a[i].y; } sort(book,book+tot); int reu=unique(book,book+tot)-book; for(int i=1;i<=n;++i) { a[i].x=lower_bound(book,book+reu,a[i].x)-book; a[i].y=lower_bound(book,book+reu,a[i].y)-book; } for(int i=1;i<=reu;++i) fa[i]=i; sort(a+1,a+n+1,cmp); for(int i=1;i<=n;++i) { int fa1=Find(a[i].x),fa2=Find(a[i].y); if(a[i].e) fa[fa2]=fa1; else if(fa1==fa2) { printf("NO\n"); flag=1; break; } } if(!flag) printf("YES\n"); } return 0; }