題目描述

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

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

樣例輸入

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

樣例輸出

NO
YES

---

題解

并查集

由于題目沒有像某食物鏈一樣規(guī)定了順序，只是問能否同時全部成立。

所以可以隨意的改變條件的順序。

那我們就可以先把所有相等關系的條件挑出來，并在并查集中合并。

然后再判定所有的不等關系，看它們的祖先是否相同。

然而題目中i和j的值太大，所以需要離散化，方法有多種，不多說了。

#include <cstdio> #include <algorithm> using namespace std; struct data {int num , p; }v[2000010]; int f[2000010] , q[2000010] , e[1000010] , tot; int find(int x) {return x == f[x] ? x : f[x] = find(f[x]); } void merge(int x , int y) {int tx = find(x) , ty = find(y);f[tx] = ty; } bool cmp(data a , data b) {return a.num < b.num; } int main() {int t;scanf("%d" , &t);while(t -- ){int n , i , flag = 1;tot = 0;scanf("%d" , &n);for(i = 1 ; i <= n ; i ++ ){scanf("%d%d%d" , &v[i].num , &v[i + n].num , &e[i]);v[i].p = i;v[i + n].p = i + n;}sort(v + 1 , v + 2 * n + 1 , cmp);for(i = 1 ; i <= 2 * n ; i ++ ){if(v[i].num != v[i - 1].num) tot++;q[v[i].p] = tot;}for(i = 1 ; i <= tot ; i ++ )f[i] = i;for(i = 1 ; i <= n ; i ++ )if(e[i] == 1)merge(q[i] , q[i + n]);for(i = 1 ; i <= n ; i ++ ){if(!e[i] && find(q[i]) == find(q[i + n])){flag = 0;break;}}printf("%s\n" , flag ? "YES" : "NO");}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/GXZlegend/p/6408367.html

總結

以上是生活随笔為你收集整理的【bzoj4195】[Noi2015]程序自动分析 离散化+并查集的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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