我们相距十万光年

晨露正葱茏，来日胜景定无穷

01/22
20:32
NOIP/NOI

NOI 2015 程序自动分析

saruka 撰写 无回复

传送门：https://www.luogu.org/problem/show?pid=1955

题解一：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int maxn = 1000100;
const int mod = 1000000;
int n, T, x, y, e, cnt;
int ueq[maxn][2], fa[maxn << 1];
 
inline int getint()
{
    int r = 0, k = 1;
    char c = getchar();
    for(; c < '0' || c > '9'; c = getchar())
        if(c == '-') k = -1;
    for(; c >= '0' && c <= '9'; c = getchar())
        r = r * 10 + c - '0';
    return r * k;
}
 
inline int hash(int x)
{
    return x > mod ? (mod + x / mod + x % mod): x;
}
 
int get_father(int x)
{
    return fa[x] = (fa[x] == x) ? x : get_father(fa[x]);
}
 
int main(int argc, char const * argv[])
{
    T = getint();
    while(T--)
    {
        cnt = 0;
        n = getint();
        for(int i = 1; i < maxn << 1; i++) fa[i] = i;
        for(int i = 1; i <= n; i++)
        {
            x = getint();
            y = getint();
            e = getint();
            x = hash(x);
            y = hash(y);
 
            if(e == 1) fa[get_father(x)] = get_father(y);
            else
            {
                ++cnt;
                ueq[cnt][0] = x;
                ueq[cnt][1] = y;  
            }
        }  
 
        bool flag = 1;
        for(int i = 1; i <= cnt; i++)
        {
            if(get_father(ueq[i][0]) == get_father(ueq[i][1]))
            {
                flag = 0;
                break;
            }
        }
        
        printf(flag ? ("YES\n") : ("NO\n"));    
    }
    return 0;
}

题解二：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
const int maxn = 1000010;
int n, sz, tp;
int tmp[maxn << 1], Hash[maxn << 1], p[maxn << 1];
 
struct Node
{
    int x, y;
    bool tp;
} s[maxn];
 
inline int getint()
{
    int r = 0, k = 1;
    char c = getchar();
    for(; c < '0' || c > '9'; c = getchar())
        if(c == '-') k = -1;
    for(; c >= '0' && c <= '9'; c = getchar())
        r = r * 10 + c - '0';
    return r * k;
}
 
int Find_Hash(int x)
{
    int l = 1, r = tp, mid;
    while(r - l > 1)
    {
        mid = (l + r) >> 1;
        if(Hash[mid] > x) r = mid;
        else if(Hash[mid] < x) l = mid;
        else if(Hash[mid] == x) return mid;
    }
    if(Hash[l] == x) return l;
    return r;
}
 
bool cmp(const Node &A, const Node &B)
{
    return A.tp > B.tp;
}
 
inline int find(int x)
{
    int r = x, pre;
    while(p[r] != r) r = p[r];
    while(x != r)
    {
        pre = p[x];
        p[x] = r;
        x = pre;
    }
    return r;
}
 
int main(int argc, char const * argv[])
{
    int T = getint();
    int fx, fy;
    while(T--)
    {
        n = getint();
        sz = 0;
 
        for(int i = 1; i <= n; i++)
        {
            s[i].x = getint();
            s[i].y = getint();
            s[i].tp = getint();
            tmp[++sz] = s[i].x;
            tmp[++sz] = s[i].y;
        }
 
        sort(tmp + 1, tmp + sz + 1);
        tp = 1;
        Hash[tp] = tmp[1];
 
        for(int i = 2; i <= sz; i++)
        {
            if(tmp[i] != tmp[i - 1])
            {
                Hash[++tp] = tmp[i];
            }
        }
 
        sort(s + 1, s + n + 1, cmp);
        for(int i = 1; i <= tp; i++) p[i] = i;
        int rec = 0, fool = 0;
 
        for(int i = 1; s[i].tp == 1 && i <= n; i++)
        {
            fx = find(Find_Hash(s[i].x));
            fy = find(Find_Hash(s[i].y));
            p[fx] = fy;
            rec = i;
        }
 
        for(int i = rec + 1; i <= n; i++)
        {
            fx = find(Find_Hash(s[i].x));
            fy = find(Find_Hash(s[i].y));
            if(fx == fy)
            {
                fool = 1;
                puts("NO\n");
                break;
            }
        }
        
        if(!fool) puts("YES\n");
    }
    return 0;
}