題目描述

在實現(xiàn)程序自動分析的過程中，常常需要判定一些約束條件是否能被同時滿足。

考慮一個約束滿足問題的簡化版本：假設(shè)x1,x2,x3...代表程序中出現(xiàn)的變量，給定n個形如xi=xj或xi≠xj的變量相等/不等的約束條件，請判定是否可以分別為每一個變量賦予恰當?shù)闹?#xff0c;使得上述所有約束條件同時被滿足。例如，一個問題中的約束條件為：x1=x2,x2=x3,x3=x4,x4≠x1，這些約束條件顯然是不可能同時被滿足的，因此這個問題應(yīng)判定為不可被滿足。

現(xiàn)在給出一些約束滿足問題，請分別對它們進行判定。

輸入輸出格式

輸入格式：

輸入文件的第1行包含1個正整數(shù)t，表示需要判定的問題個數(shù)。注意這些問題之間是相互獨立的。

對于每個問題，包含若干行：

第1行包含1個正整數(shù)n，表示該問題中需要被滿足的約束條件個數(shù)。接下來n行，每行包括3個整數(shù)i,j,e，描述1個相等/不等的約束條件，相鄰整數(shù)之間用單個空格隔開。若e=1，則該約束條件為xi=xj；若�e=0，則該約束條件為xi≠xj；

輸出格式：

輸出文件包括t行。

輸出文件的第 k行輸出一個字符串“ YES” 或者“ NO”（不包含引號，字母全部大寫），“ YES” 表示輸入中的第k個問題判定為可以被滿足，“ NO” 表示不可被滿足。

輸入輸出樣例

輸入樣例#1：

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

輸出樣例#1：

NO
YES

輸入樣例#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

思路：

首先將所有的 e=1 的操作放在前面，當進行 e=1 的操作時，只要將他約束的兩個變量放在同一個集合中即可，然后再進行 e=0 的操作，當 e=0 時，對于他約束的兩個變量，如果在同一個集合中，就不可能滿足，輸出 NO，若不在同一個集合中，輸出 YES

由于數(shù)據(jù)范圍達到 1E9，直接開 1E9 的 father 數(shù)組是不現(xiàn)實的，因此需要進行離散化

源代碼

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-9 #define INF 0x3f3f3f3f #define LL long long const int MOD=10007; const int N=1000000+5; const int dx[]= {-1,1,0,0}; const int dy[]= {0,0,-1,1}; using namespace std; struct Node{int a,b;int op;//操作符bool operator < (const Node &rhs)const{//按操作排序return op>rhs.op;} }a[N]; int father[N]; int Rank[N*2]; int Find(int x){if(x==father[x])return x;return father[x]=Find(father[x]); } void Union(int x,int y){x=Find(x);y=Find(y);if(x!=y)father[x]=y; } int main(){int t;scanf("%d",&t);while(t--){memset(Rank,0,sizeof(Rank));int n;scanf("%d",&n);int cnt=1;for(int i=1;i<=n;i++){scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].op);Rank[cnt++]=a[i].a;Rank[cnt++]=a[i].b;}cnt--;//離散化sort(Rank+1,Rank+cnt+1);int len=unique(Rank+1,Rank+cnt+1)-Rank;for(int i=1;i<=n;i++){a[i].a=lower_bound(Rank,Rank+len,a[i].a)-Rank;a[i].b=lower_bound(Rank,Rank+len,a[i].b)-Rank;}for(int i=1;i<=len;i++)//初始化father[i]=i;sort(a+1,a+n+1);//按op排序bool flag=true;for(int i=1;i<=n;i++){int x=Find(a[i].a);int y=Find(a[i].b);if(a[i].op==1){//合并Union(x,y);}else{//查詢if(x==y){flag=false;printf("NO\n");break;}}}if(flag)printf("YES\n");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的程序自动分析（洛谷-P1955）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。