CCCC-GPLT L2-010 排座位 小并查集_ccccgplt什么意思

输入第一行给出3个正整数：N（<= 100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：“宾客1 宾客2 关系”，其中“关系”为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行，每行给出一对需要查询的宾客编号。
这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。

观察题目发现,两个人是否为朋友和两个人是否为敌人是相互独立的.朋友关系用并查集存储,敌人关系用二维表存储即可(n<=100).
有一个小trick,两个人的情况一共有4种状态,对应4个输出,用两位的二进制码控制输出数组会很方便.

/* LittleFall : Hello! */
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read();
inline void write(int x);
const int M = 100016;
int fa[M];
int getfa(int p)
{
    if(fa[p]==p) return p;
    return fa[p]=getfa(fa[p]);
}
const char output[4][20]={"OK but...","No problem","No way","OK"};
int isopp[128][128];
int main(void)
{
    #ifdef _LITTLEFALL_
    printf("ok compile suc\n\n");
    freopen("in.txt","r",stdin);
    #endif
    //std::cin.sync_with_stdio(false); 

    int n=read(),m=read(),k=read();
    for(int i=1;i<=100;i++)
        fa[i]=i;
    for(int i=0;i<m;i++)
    {
        int ta=read(),tb=read(),t=read();
        if(t==-1)
        {
            isopp[ta][tb]=1;
            isopp[tb][ta]=1;
        }
        else
        {
            int faa=getfa(ta),fbb=getfa(tb);
            if(faa!=fbb)
            {
                if(faa>fbb) swap(faa,fbb);
                fa[fbb]=faa;
            }
        }
    }
    for(int i=0;i<k;i++)
    {
        int ta=read(),tb=read();
        int status=((getfa(ta)!=getfa(tb))*2)+!isopp[ta][tb];
        printf("%s\n",output[status] );
    }
    return 0;
}


inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void write(int x)
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
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