★☆   输入文件：prog.in   输出文件：prog.out   简单对比

时间限制：2 s   内存限制：512 MB

【题目描述】

在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设x1,x2,x3,...xn代表程序中出现的变量，给定n个形如xi=xj或者xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述条件同时被满足。

【输入格式】

输入文件第一行包含一个正整数T,表示需要判定的问题个数。注意这些问题之间相互独立。

对于每个问题，包含若干行：

第一行一个正整数n,表示约束条件个数。

接下来n行，每行三个正整数i,j,e,描述一个相等/不等的约束条件。若e=1,则约束条件为xi=xj，若e=0,则约束条件为xi≠xj

【输出格式】

输出文件包括T行。

输出文件的第k行输出一个字符串"YES"或者"NO"(不包含引号，字母全部大写).

【样例输入1】

221 2 11 2 021 2 12 1 1

【样例输出1】

NOYES

【样例输入2】

2

3

1 2 1

2 3 1

3 1 1

4

1 2 1

2 3 1

3 4 1

1 4 0

【样例输出2】

YES

NO

数据规模

1<=T<=10

对于1,2:1<=n<10

对于3,4:10<n<=100

对于5,6,7:100<n<=100,000

对于8,9,10:100<n<=100,000

对于前70%的数据：1<=i,j<=10,000

对于100%的数据：1<=i,j<=1,000,000,000

【来源】

NOI2015

思路

hash+并查集

代码实现

1     #include
     
       2     #include
      
        3     #include
       
         4     using namespace std; 5     const int maxn=3e6; 6     const int mod=2999957; 7     int test,n,ans; 8     int a,b,c; 9     int f[maxn];10     struct question{
   int a,b,c;}q[maxn];11     int hash(int a){12         int ha=1;13         while(a){14             ha*=a;15             ha%=mod;16             a/=10;17         }18         return ha;19     }20     int find(int x){
   return f[x]==x?x:f[x]=find(f[x]);}21     bool comp(const question&x,const question&y){
   return x.c>y.c;}22     int main(){23         freopen("prog.in","r",stdin);24         freopen("prog.out","w",stdout);25         scanf("%d",&test);26         while(test--){27             memset(f,0,sizeof(f));28             ans=1;29             scanf("%d",&n);30             for(int i=1;i<=n;i++){31                 scanf("%d%d%d",&a,&b,&c);32                 q[i]=(question){hash(a),hash(b),c};33             }34             sort(q+1,q+n+1,comp);35             for(int i=1;i<=n;i++){36                 a=q[i].a,b=q[i].b;37                 if(!f[a]) f[a]=a;38                 if(!f[b]) f[b]=b;39                 a=find(a),b=find(b);40                 if(q[i].c) f[b]=a;41                 else if(a==b) ans=0;42                 if(!ans) break;43             }44             if(ans) puts("YES");45             else puts("NO");46         }47         return 0;48     }
       
      
     

单模居然没W；

因为忘了写find_f的修正路径，差点降低本题通过率。。。

NOI2015