[NOI2015]程式自動分析(luogu p1955并查集&離散化)

題目傳送門

題目描述

在實作程式自動分析的過程中，常常需要判定一些限制條件是否能被同時滿足。

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

現在給出一些限制滿足問題，請分别對它們進行判定。

輸入格式

從檔案prog.in中讀入資料。

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

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

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

輸出格式

輸出到檔案 prog.out 中。

輸出檔案包括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

說明/提示

【樣例解釋1】

在第一個問題中，限制條件為：x1=x2,x1≠x2。這兩個限制條件互相沖突，是以不可被同時滿足。

在第二個問題中，限制條件為：x1=x2,x1=x2。這兩個限制條件是等價的，可以被同時滿足。

【樣例說明2】

在第一個問題中，限制條件有三個：x1=x2,x2=x3,x3=x1。隻需指派使得x1=x1=x1，即可同時滿足所有的限制條件。

在第二個問題中，限制條件有四個：x1=x2,x2=x3,x3=x4,x4≠x1。由前三個限制條件可以推出x1=x2=x3=x4，然而最後一個限制條件卻要求x1≠x4，是以不可被滿足。

分析：用并查集解決，if(e1)就把i,j放在一個集合裡，先處理所有e=1的，然後e=0時，如果查到ij說明不符合，輸出no，查詢完仍符合的，輸出yes

重點：由于資料範圍1e9，不能用數組存下，肯定會爆空間記憶體，是以需要對資料進行離散化處理

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <string.h>
#include <map>
#include <math.h>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <deque>
using namespace std;
typedef long long ll;
const int N=1e7+7;
struct sa
{
    int x,y,e;
}p[N];
int cmp(sa a,sa b)
{
    return a.e>b.e;
}
int a[N],f[N];
int find(int x)
{
    if(f[x]==x)
        return x;
    else
        return f[x]=find(f[x]);//路徑壓縮
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(p,0, sizeof(p));
        memset(a,0, sizeof(a));
        memset(f,0, sizeof(f));
        int n;
        int cnt=1;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].e);
            a[cnt++]=p[i].x;
            a[cnt++]=p[i].y;
        }
        cnt--;
        sort(a+1,a+cnt+1);                           //離散化
        int s=unique(a+1,a+cnt+1)-a-1;
        for(int i=1;i<=n;i++)
        {
            p[i].x=lower_bound(a+1,a+s+1,p[i].x)-a;
            p[i].y=lower_bound(a+1,a+s+1,p[i].y)-a;
        }
        for(int i=1;i<=s;i++)
            f[i]=i;
        sort(p+1,p+n+1,cmp);
        int flag=1;
        for(int i=1;i<=n;i++)
        {
            int x=find(p[i].x);
            int y=find(p[i].y);
            if(p[i].e==1)                       //先把相等的放在同一個集合裡
            {
                f[x]=y;
            }
            else
            {
                if(x==y) {
                    printf("NO\n");
                    flag = 0;
                    break;
                }
            }
        }
        if(flag==1)
            printf("YES\n");
    }
    return 0;
}