并查集有关

食物链

分析：
存在A吃B，B吃C，C吃A这三种关系，即存在三种生物，三个集合，而这三种生物又是等价的，对于每一个生物x，他都可以是A，也可以是B，也可以是C，假定fa[x],fa[n + x], fa[2 * n + x]分别是生物x是A,B,C的情况下的父节点。对于每次的两个生物都要把他们当作A,B,C分别看一遍。
eg.
2 2 3
1 1 3
第一句话表示2吃3，即2是A的时候，3不能是A,和C，2是B的时候，3不能是B和A，2是C的时候，3不能是C和B,判断后合并
第二句话同样判断
AC代码：

#include <cstdio>

using namespace std;

int n, k;
int fa[150050];
int ans;
int d, x, y;

int findfa(int x)
{
    return x == fa[x] ? x : fa[x] = findfa(fa[x]);
}

void merge_(int x,int y)
{
    fa[findfa(y)] = findfa(x);
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= 3 * n; ++i) fa[i] = i;
    for(int i = 1; i <= k; ++i)
    {
        scanf("%d%d%d", &d, &x, &y);
        if(x > n || y > n)  ans++;
        else if(d == 2 && x == y)   ans++;
        else if(d == 1)
        {
            if(findfa(x) == findfa(y + n) || findfa(x) == findfa(2 * n + y))    ans++;
            else
            {
                merge_(x, y);
                merge_(x + n, y + n);
                merge_(x + 2 * n, y + 2 * n);
            }
        }
        else if(d == 2)
        {
            if(findfa(x) == findfa(y) || findfa(x) == findfa(2 * n + y))    ans++;
            else
            {
                merge_(x, y + n);
                merge_(x + n, y + 2 * n);
                merge_(x + 2 * n, y);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

关押罪犯

分析：
方法1：同食物链
AC代码：

#include <bits/stdc++.h>

using namespace std;

int n, m;
struct node
{
    int a, b, c;
}ar[100050];
int fa[40050];
bool flag;

bool cmp(struct node A, struct node B)
{
    return A.c > B.c;
}

int findfa(int x)
{
    return fa[x] == x ? x : fa[x] = findfa(fa[x]);
}

void merge_(int x, int y)
{
    fa[findfa(y)] = findfa(x);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i) scanf("%d%d%d", &ar[i].a, &ar[i].b, &ar[i].c);
    for(int i = 1; i <= 2 * n; ++i) fa[i] = i;
    sort(ar + 1, ar + m + 1, cmp);
    for(int i = 1; i <= m; ++i)
    {
        if(findfa(ar[i].a) == findfa(ar[i].b) || findfa(ar[i].a + n) == findfa(ar[i].b + n))
        {
            printf("%d\n", ar[i].c);
            flag = 1;
            break;
        }
        else
        {
            merge_(ar[i].a, ar[i].b + n);
            merge_(ar[i].a + n, ar[i].b);
        }
    }
    if(!flag)   printf("0\n");
    return 0;
}

二分图

关押罪犯

方法二：二分图
如果a，b打架会造成影响值c，那么就在a，b之间连一条长为c的边。
然后利用二分的思想，那剩下的就是如何判断。
我们利用一个数组color[i]来记录点i的颜色（1或2），如果两个点之间有边的话，一个点的颜色是1，另一个点就必须是2，不然就表明这两个点在一块了，即两个人在一个监狱。
AC代码：

#include <bits/stdc++.h>

using namespace std;

int n, m;
int a, b, c;
int tot;
int head[20050];
struct node
{
    int to, l, next;
}edge[200050];
int color[20050];
int l, mid, r;

void addedge(int u, int v, int w)
{
    edge[++tot].to = v;
    edge[tot].l = w;
    edge[tot].next = head[u];
    head[u] = tot;
}

//进入dfs，首先把点u染成颜色c，然后遍历与点u相连的点
//如果某个相连的点的边权小于了k跳过就好，因为要让最大的最小，这个一定不是最大的
//在判断该点是否染色，染了的话看是不是一样，一样直接return false
//如果没染色，就染色，做同样的操作（递归）
//另外，对于染色了但是不冲突的，不用管就好，仔细想想确实不用管哈
bool dfs(int u, int c, int k)
{
    color[u] = c;

    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        if(edge[i].l <= k)  continue;
        if(color[edge[i].to])
        {
            if(color[edge[i].to] == c)  return false;
        }
        else if(!dfs(edge[i].to, 3 - c, k)) return false;
    }
    return true;
}

bool check(int k)
{
    memset(color, 0, sizeof(color));

    for(int i = 1; i <= n; ++i)
    {
        if(!color[i])
        {
            if(!dfs(i, 1, k))
                return false;
        }
    }
    return true;
}

int main()
{
    memset(edge, -1, sizeof(edge));
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &a, &b, &c);
        addedge(a, b, c);
        addedge(b, a, c);
    }
    l = 0, r = 1e9;
    //这里二分条件写l<=r的话，带等号，下面l一定要等于mid + 1，r一定要等于mid - 1；
    while(l <= r)
    {
        mid = (l + r) >> 1;
        //cout << mid << endl;
        if(check(mid))  r = mid - 1;
        else    l = mid + 1;
    }
    printf("%d\n", r + 1);
    return 0;
}