题目描述
在实现程序自动分析的过程中, 常常需要判定一些约束条件是否能被同时满足.
考虑一个约束满足问题的简化版本: 假设 x1,x2,x3... 代表程序中出现的变量, 给定 n 个形如 xi=xj 或 xixj 的变量相等 / 不等的约束条件, 请判定是否可以分别为每一个变量赋予恰当的值, 使得上述所有约束条件同时被满足. 例如, 一个问题中的约束条件为: x1=x2,x2=x3,x3=x4,x4x1, 这些约束条件显然是不可能同时被满足的, 因此这个问题应判定为不可被满足.
现在给出一些约束满足问题, 请分别对它们进行判定.
输入输出格式
输入格式:
从文件 prog.in 中读入数据.
输入文件的第 1 行包含 1 个正整数 t, 表示需要判定的问题个数. 注意这些问题之间是相互独立的.
对于每个问题, 包含若干行:
第 1 行包含 1 个正整数 n, 表示该问题中需要被满足的约束条件个数. 接下来 n 行, 每行包括 3 个整数 i,j,e, 描述 1 个相等 / 不等的约束条件, 相邻整数之间用单个空格隔开. 若 e=1, 则该约束条件为 xi=xj; 若e=0, 则该约束条件为 xixj;
输出格式:
输出到文件 prog.out 中.
输出文件包括 t 行.
输出文件的第 k 行输出一个字符串 "YES" 或者 "NO"(不包含引号, 字母全部大写),"YES" 表示输入中的第 k 个问题判定为可以被满足,"NO" 表示不可被满足.
思路:
这道题能作为 NOI2015 的题, 我也是醉了
难度还不如 NOIP
显而易见的这道题是一个带扩展域的并查集
先把所有的满足用并查集跑一边, 在跑不满足的
如果不满足条件已经被满足, 就说明肯定有冲突, 输出即可
特别注意:
别看他数据范围大的吓人, 其实没什么大不了的, 模个数离散化一下即可
代码:
- #include<iostream>
- #include<cstdio>
- #define rii register int i
- #define rij register int j
- using namespace std;
- int n,opt,t;
- long long v1,v2;
- int mod=926817;
- int x[1000005],f[1000005],bcl1[1000005],jsq,bcl2[1000005];
- int find(int x)// 并查集标配
- {
- if(f[x]!=x)
- {
- f[x]=find(f[x]);
- }
- return f[x];
- }
- int main()
- {
- scanf("%d",&t);
- for(rii=1;i<=t;i++)
- {
- jsq=0;
- for(rij=1;j<=1000005;j++)
- {
- f[j]=j;
- }
- scanf("%d",&n);
- for(rij=1;j<=n;j++)
- {
- scanf("%lld%lld%d",&v1,&v2,&opt);
- v1=v1%mod;
- v2=v2%mod;
- if(opt==1)
- {
- int ltt=find(v1);
- int kkk=find(v2);
- f[ltt]=kkk;
- }
- else
- {
- jsq++;
- bcl1[jsq]=v1;// 存拓展域 (其实就是补集)
- bcl2[jsq]=v2;
- }
- }
- int bj=0;
- for(rij=1;j<=jsq;j++)
- {
- if(find(bcl1[j])==find(bcl2[j]))
- {
- printf("NO\n");
- bj=1;
- break;
- }
- }
- if(bj!=1)
- {
- printf("YES\n");
- }
- }
- }
来源: https://www.cnblogs.com/ztz11/p/9030504.html