HDU - 1824 Let's go home 做题记录

· · 个人记录

题目链接：https://vjudge.net/problem/HDU-1824

差点忘了还有这道题，这道题比起题目难度，更难的是有歧义的题干，一对人不是必须一走一留，而是可以都走但不能都留。一队人必须队长留或两个队员留，也可以都留，其他的方法连边太繁琐，而且可能有误，比如他们认为一个队员走，另一个必须走。

我们设 i 为走，i+n 为留，那么队长走，其他两个队员就得留，队员走，队长必须留。一对人，一个留，另一个必须走。其他的就很基础了。

代码：

//Just Sayori
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <random>
#define ll long long
#define rnt register int
#define gr getchar
#define pr putchar
#define N 500005
#define M 1000000007
using namespace std;

inline ll read()
{
    ll x = 0, f = 1;
    char ch = gr();
    while (ch < '0' || ch > '9')
        ch == '-' ? f = -1, ch = gr() : ch = gr();
    while (ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = gr();
    return x * f;
}

inline void write(ll x)
{
    static int sta[39], top = 0;
    if (x < 0)
        pr('-'), x = -x;
    do
        sta[++top] = x % 10, x /= 10;
    while (x);
    while (top)
        pr(sta[top--] ^ 48);
}

struct edge
{
    int v, next;
} e[N << 1];
int head[N], cnt;

inline void add(int u, int v)
{
    e[++cnt] = {v, head[u]}, head[u] = cnt;
}
int n, m, a, b, c, t, bcc, top;
int dfn[N], low[N], num[N], vis[N], stack[N];

void tarjan(int u)
{
    dfn[u] = low[u] = ++cnt;
    vis[u] = 1, stack[++top] = u;
    for (rnt i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v;
        if (!dfn[v])
            tarjan(v), low[u] = min(low[u], low[v]);
        else if (vis[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        bcc++;
        while (stack[top + 1] != u)
            num[stack[top]] = bcc, vis[stack[top--]] = 0;
    }
}

int main()
{
    while (cin >> t)
    {
        bool f = 1;
        m = read(), n = 3 * t;
        for (rnt i = 1; i <= t; i++)
        {
            a = read() + 1, b = read() + 1, c = read() + 1;
            add(a, b + n), add(a, c + n);
            add(b, a + n), add(c, a + n);
        }
        for (rnt i = 1; i <= m; i++)
        {
            a = read() + 1, b = read() + 1;
            add(a + n, b), add(b + n, a);
        }
        for (rnt i = 1; i <= 2 * n; i++)
            if (!dfn[i])
                tarjan(i);
        for (rnt i = 1; i <= n; i++)
            if (num[i] == num[i + n])
                f = 0;
        if (f)
            puts("yes");
        else
            puts("no");
        for (rnt i = 1; i <= 2 * n; i++)
            dfn[i] = num[i] = vis[i] = head[i] = stack[i] = 0;
        bcc = cnt = top = 0;
    }
    return 0;
}