企业官网建设流程全解析

P1955 [NOI2015] 程序自动分析

题目描述

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

考虑一个约束满足问题的简化版本：假设x1,x2,x3,⋯x_1,x_2,x_3,\cdotsx1​,x2​,x3​,⋯代表程序中出现的变量，给定nnn个形如xi=xjx_i=x_jxi​=xj​或xi≠xjx_i\neq x_jxi​=xj​的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2,x2=x3,x3=x4,x4≠x1x_1=x_2,x_2=x_3,x_3=x_4,x_4\neq x_1x1​=x2​,x2​=x3​,x3​=x4​,x4​=x1​，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

输入格式

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

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

第一行包含一个正整数nnn，表示该问题中需要被满足的约束条件个数。接下来nnn行，每行包括三个整数i,j,ei,j,ei,j,e，描述一个相等/不等的约束条件，相邻整数之间用单个空格隔开。若e=1e=1e=1，则该约束条件为xi=xjx_i=x_jxi​=xj​。若e=0e=0e=0，则该约束条件为xi≠xjx_i\neq x_jxi​=xj​。

输出格式

输出包括ttt行。

输出文件的第kkk行输出一个字符串YES或者NO（字母全部大写），YES表示输入中的第kkk个问题判定为可以被满足，NO表示不可被满足。

输入输出样例 #1

输入 #1

2 2 1 2 1 1 2 0 2 1 2 1 2 1 1

输出 #1

NO YES

输入输出样例 #2

输入 #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】

在第一个问题中，约束条件为：x1=x2,x1≠x2x_1=x_2,x_1\neq x_2x1​=x2​,x1​=x2​。这两个约束条件互相矛盾，因此不可被同时满足。

在第二个问题中，约束条件为：x1=x2,x1=x2x_1=x_2,x_1 = x_2x1​=x2​,x1​=x2​。这两个约束条件是等价的，可以被同时满足。

【样例说明2】

在第一个问题中，约束条件有三个：x1=x2,x2=x3,x3=x1x_1=x_2,x_2= x_3,x_3=x_1x1​=x2​,x2​=x3​,x3​=x1​。只需赋值使得x1=x2=x3x_1=x_2=x_3x1​=x2​=x3​，即可同时满足所有的约束条件。

在第二个问题中，约束条件有四个：x1=x2,x2=x3,x3=x4,x4≠x1x_1=x_2,x_2= x_3,x_3=x_4,x_4\neq x_1x1​=x2​,x2​=x3​,x3​=x4​,x4​=x1​。由前三个约束条件可以推出x1=x2=x3=x4x_1=x_2=x_3=x_4x1​=x2​=x3​=x4​，然而最后一个约束条件却要求x1≠x4x_1\neq x_4x1​=x4​，因此不可被满足。

【数据范围】

所有测试数据的范围和特点如下表所示：

::cute-table{tuack}

C++实现

#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<string>#include<cmath>#include<cstdlib>usingnamespacestd;intt,n,f[1000007],book[1000007*3];//t表示t组数据，n表示有n个操作，f[]是我们并查集的数字，book[]是离散化的数组structnode{intx,y,e;}a[1000001];boolcmp(node a,node b){returna.e>b.e;}//排 序将e==1的放在前面inlinevoidfirst(intkkk){for(inti=1;i<=kkk;i++)f[i]=i;}//初 始 化intget(intx){if(x==f[x])returnx;returnf[x]=get(f[x]);}intmain(){scanf("%d",&t);while(t--){inttot=-1;memset(book,0,sizeof(book));memset(a,0,sizeof(a));memset(f,0,sizeof(f));intflag=1;scanf("%d",&n);for(inti=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);//排序intreu=unique(book,book+tot)-book;//去重for(inti=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;}first(reu);//初始化sort(a+1,a+n+1,cmp);//按e排序for(inti=1;i<=n;i++){intr1=get(a[i].x);intr2=get(a[i].y);if(a[i].e){f[r1]=r2;//就是我们的merge操作}elseif(r1==r2){printf("NO\n");flag=0;//如果不满足条件，标记为否break;}}if(flag)printf("YES\n");//都满足条件了}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容