组建 网站开发团队,交互设计作品集网站,网站设计培训班老师,中企动力做的网站价格区间Description 在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。 考虑一个约束满足问题的简化版本#xff1a;假设x1,x2,x3,…代表程序中出现的变量#xff0c;给定n个形如xixj或xi≠xj的变量相等/不等的约束条件#xff0c;请判定是否可以分别为每一个…Description 在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。 考虑一个约束满足问题的简化版本假设x1,x2,x3,…代表程序中出现的变量给定n个形如xixj或xi≠xj的变量相等/不等的约束条件请判定是否可以分别为每一个变量赋予恰当的值使得上述所有约束条件同时被满足。例如一个问题中的约束条件为x1x2x2x3x3x4x1≠x4这些约束条件显然是不可能同时被满足的因此这个问题应判定为不可被满足。 现在给出一些约束满足问题请分别对它们进行判定。 Input 输入文件的第1行包含1个正整数t表示需要判定的问题个数。注意这些问题之间是相互独立的。 对于每个问题包含若干行 第1行包含1个正整数n表示该问题中需要被满足的约束条件个数。 接下来n行每行包括3个整数i,j,e描述1个相等/不等的约束条件相邻整数之间用单个空格隔开。若e1则该约束条件为xixj若e0则该约束条件为xi≠xj。 Output 输出文件包括t行。 输出文件的第k行输出一个字符串“YES”或者“NO”不包含引号字母全部大写“YES”表示输入中的第k个问题判定为可以被满足“NO”表示不可被满足。 Sample Input 2 2 1 2 1 1 2 0 2 1 2 1 2 1 1 Sample Output NO YES HINT 在第一个问题中约束条件为x1x2,x1≠x2。这两个约束条件互相矛盾因此不可被同时满足。 在第二个问题中约束条件为x1x2,x2x1。这两个约束条件是等价的可以被同时满足。 1≤n≤1000000 1≤i,j≤1000000000 Solution 水题一道 由于等号具有连续性所以先处理所有相等的限制用并查集维护哪些是相等的 然后判断不等号如果有不等号两边在同一并查集内显然就不行 #includebits/stdc.h
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define REP(a,b,c) for(register int a(b),a##end(c);aa##end;a)
#define DEP(a,b,c) for(register int a(b),a##end(c);aa##end;--a)
const int MAXN40000010;
int T,n,fa[MAXN],lt;
std::vectorint V;
std::mapint,int M;
struct node{int x,y,opt;inline bool operator (const node A) const {return optA.opt;};
};
node limit[MAXN];
templatetypename T inline void read(T x)
{T data0,w1;char ch0;while(ch!-(ch0||ch9))chgetchar();if(ch-)w-1,chgetchar();while(ch0ch9)data((T)data3)((T)data1)(ch^0),chgetchar();xdata*w;
}
templatetypename T inline void write(T x,char ch\0)
{if(x0)putchar(-),x-x;if(x9)write(x/10);putchar(x%100);if(ch!\0)putchar(ch);
}
templatetypename T inline void chkmin(T x,T y){x(yx?y:x);}
templatetypename T inline void chkmax(T x,T y){x(yx?y:x);}
templatetypename T inline T min(T x,T y){return xy?x:y;}
templatetypename T inline T max(T x,T y){return xy?x:y;}
inline void discretization()
{V.clear();M.clear();REP(i,1,n)V.push_back(limit[i].x),V.push_back(limit[i].y);std::sort(V.begin(),V.end());V.erase(std::unique(V.begin(),V.end()),V.end());REP(i,0,V.size()-1)M[V[i]]i1;ltV.size();REP(i,1,n)limit[i].xM[limit[i].x],limit[i].yM[limit[i].y];
}
inline int found(int x)
{if(fa[x]!x)fa[x]found(fa[x]);return fa[x];
}
int main()
{read(T);while(T--){read(n);REP(i,1,n){int x,y,opt;read(x);read(y);read(opt);limit[i](node){x,y,opt};}discretization();std::sort(limit1,limitn1);REP(i,1,lt)fa[i]i;int mk1;REP(i,1,n){int ulimit[i].x,vlimit[i].y;if(limit[i].opt)fa[found(u)]found(v);else if(found(u)found(v)){mk0;break;}}puts(mk?YES:NO);}return 0;
} 转载于:https://www.cnblogs.com/hongyj/p/9688387.html
