4195: [Noi2015]程序自動分析

?

Description

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

考慮一個約束滿足問題的簡化版本：假設x1,x2,x3,…代表程序中出現的變量，給定n個形如xi=xj或xi≠xj的變量相等/不等的約束條件，請判定是否可以分別為每一個變量賦予恰當的值，使得上述所有約束條件同時被滿足。例如，一個問題中的約束條件為：x1=x2，x2=x3，x3=x4，x1≠x4，這些約束條件顯然是不可能同時被滿足的，因此這個問題應判定為不可被滿足。 現在給出一些約束滿足問題，請分別對它們進行判定。

Input

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

對于每個問題，包含若干行： 第1行包含1個正整數n，表示該問題中需要被滿足的約束條件個數。 接下來n行，每行包括3個整數i,j,e，描述1個相等/不等的約束條件，相鄰整數之間用單個空格隔開。若e=1，則該約束條件為xi=xj；若e=0，則該約束條件為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

?在第一個問題中，約束條件為：x1=x2,x1≠x2。這兩個約束條件互相矛盾，因此不可被同時滿足。

在第二個問題中，約束條件為：x1=x2,x2=x1。這兩個約束條件是等價的，可以被同時滿足。 1≤n≤1000000 1≤i,j≤1000000000 題解： 是并查集無疑。。 P.S.一開始考慮錯了，往經典的朋友和敵人方面上想了，但是被這個不等于搞的亂七八糟。。。。 其實只要先維護等于的關系就好了。。。。 #include<stdio.h> #include<iostream> #include<algorithm> using namespace std; const int N=1000005; struct node {int a,id; }p[N<<1]; int T,n,i,P,k,a[N],h[N<<1],f[N<<1]; inline void read(int &v){char ch,fu=0;for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());if(ch=='-') fu=1, ch=getchar();for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';if(fu) v=-v; } bool cmp(const node&x,const node&y) {return x.a<y.a; } int get(int x) {if(f[x]==x) return x;else return f[x]=get(f[x]); } int main() {read(T);while(T--){read(n);for(i=1;i<=n;i++){read(p[i*2-1].a),read(p[i*2].a),read(a[i]);p[i*2-1].id=i*2-1,p[i*2].id=i*2;}sort(p+1,p+n*2+1,cmp);k=0;for(i=1;i<=n*2;i++){if(p[i].a!=p[i-1].a) k++;h[p[i].id]=k;f[i]=i;}for(i=1;i<=n;i++)if(a[i]==1){int fx=get(h[i*2-1]),fy=get(h[i*2]);if(fx!=fy) f[fx]=fy;}P=0;for(i=1;i<=n;i++)if(a[i]==0){int fx=get(h[i*2-1]),fy=get(h[i*2]);if(fx==fy) {P=1;break;}}if(P==1) printf("NO\n");else printf("YES\n");}return 0; }

?

轉載于:https://www.cnblogs.com/lwq12138/p/5658338.html

總結

以上是生活随笔為你收集整理的bzoj 4195: [Noi2015]程序自动分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。