互相独立，互不影响的。
分析:
有n个等式/不等式，问是否可以同时满足 20% 继续爆搜 40% 不晓得这个要如何搞。。 70% floodfill算法。将所有的等式关系建成一个图。然后我们循环每一个点，如果当前点还没有被访问过，则从这个点开始，dfs遍历所有和它有边相连的点，并标记。注意，标记是不一样的。从1开始遍历就标记为1，从2开始遍历就标记为2 然后我们检查所有的不等式。如果要求不等的两个点i和j标记相同，说明它们被要求“等于”，就输出NO。如果所有要求不等的两个点都不在一个联通块内，则输出YES。 100% 标号过大？ 通过离散化重新进行标号 我们可以用并查集维护所有数之间的相等关系。先处理所有的等式，将等式两边的两个数所在的集合合并在一起 然后我们检查所有的不等式。如果某个不等式两边的数字在一个集合中（被要求相等），则输出NO。不存在这样的情况则输出YES 如果不用离散化的话(f[i],i不能从1~N,也不能从1~2*n,这个数可能很大，最低得200000)最后一个点过不了。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int t,n; int f[200010],tmp[200010]; int x[100005],y[100005],z[100005]; int fd(int x) { if(f[x]!=x) f[x]=fd(f[x]); return f[x]; } void solve() { int i; scanf("%d",&n); for(i=1;i<=n*2;i++) f[i]=i; for(i=1;i<=n;++i) { scanf("%d%d%d",&x[i],&y[i],&z[i]); tmp[i*2-1]=x[i];tmp[i*2]=y[i]; } sort(tmp+1,tmp+1+n*2); for(i=1;i<=n;i++)//就是把每个数字重新编个在1~2*n内的编号。 {//这里可以不用去重（想一想为什么？）。 x[i]=lower_bound(tmp+1,tmp+1+n*2,x[i])-tmp;//这里附上lower_bound的用法： y[i]=lower_bound(tmp+1,tmp+1+n*2,y[i])-tmp; if(z[i]) { int r1=fd(x[i]); int r2=fd(y[i]); if(r1!=r2) f[r1]=r2; } } for(i=1;i<=n;i++) { if(z[i]) continue; if(fd(x[i])==fd(y[i])) {printf("NO\n");return;} } printf("YES\n"); return; } int main() { freopen("equ.in","r",stdin); freopen("equ.out","w",stdout); scanf("%d",&t); while(t--) solve(); fclose(stdin); fclose(stdout); return 0; } 这就是一种简单的离散化（当然用哈希也不会错），其思想还是值得借鉴的。 lower_bound用法 int a[]={0,1,2,2,3}; printf("%d\n",lower_bound(a,a+5,2)-a); printf("%d\n",upper_bound(a,a+5,2)-a); 结果：2 4 lower的意义是对于给定的已经排好序的a，key最早能插入到那个位置， 0 1 | 2 2 3 所以2最早插入到2号位置。 upper的意义是对于给定的已经排好序的a，key最晚能插入到那个位置， 0 1 2 2 | 3 所以2最晚插入到4号位置。