P3513 KON-Conspiracy 做题记录

· · 个人记录

这道题，我们发现一个人有两种选择：阴谋者和支援小组，所以我们发现，这也许是一道 2-SAT 问题。不过波兰人出这种有点符合历史了。

我们发现，互相认识的人，一个成为阴谋者，另一个只能去支援小组；不认识的人，一个去支援小组，另一个只能成为支援者，建图是 O(n^2) 的，然后跑 tarjan 输出就行了，怎么可能是紫啊……
（龙图）什么叫输出方案数？

没错，这道题的难点就是方案数如何统计，那我们每个人都判断能否选两个呢？等我写到一半发现问题所在，你难以判断下文的换一个人，只能判断扔一个人，不过还好，至少可做，但是你链式前向星存图多存一个 u 会爆空间（beyond），最后拼尽全力拿了62，超时和爆空间是硬伤。
那我们该怎么做？我们发现，你可以通过把人从一个小组扔到另一个小组来统计方案数，而且我们发现把两个人一起扔过去会出问题，所以一次只能扔一个人，来回互相扔一个人相当于交换，所以我们的操作就是扔一个人和换一个人。

我们记录每个人被扔到另一边会有多少个冲突，称为矛盾点，我们发现，如果一个人没有矛盾点，那他可以直接被扔过去，如果他有一个矛盾点且他的矛盾点没有矛盾点，那么他俩可以调换，否则不行。
为什么一个没有矛盾点的人不能调换呢？我们知道矛盾点为一的人算了与它的贡献，那么矛盾点为零的人呢？
我们假设有三个人 {1,2} {3}，假设 3 没有矛盾点，如果他是阴谋者，那么它和 1、2 都认识，那么 1、2 就会有 3 作为矛盾点，所以双方同时不会出现矛盾点，所以这个无需统计。由于矛盾点为 1 和 0 才计入答案，所以矛盾点编号只需要记录最后一个。

另外还要注意两组个数，扔人时要注意本组人大于一，初始答案也要保证两组人都大于一才算入贡献。
最后发现自己链式前向星多加了个变量导致一直 MLE：

//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 5001
#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 * N];
int head[N << 1], cnt;

inline void add(int u, int v)
{
    e[++cnt] = {v, head[u]}, head[u] = cnt;
}

int n, m, c, k, x, y, ans, bcc, top, lena, lenb;
int a[N], b[N], id[N], dfn[N << 1], low[N << 1], num[N << 1], sum[N], vis[N << 1], stack[N << 1];
bool ina[N];
bool f[N][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()
{
    int n = read();
    for (rnt i = 1; i <= n; i++)
    {
        k = read();
        for (rnt j = 1; j <= k; j++)
            x = read(), f[i][x] = 1;
    }
    for (rnt i = 2; i <= n; i++)
        for (rnt j = 1; j < i; j++)
            if (f[i][j])
                add(i + n, j), add(j + n, i); //i:支援，i+n：阴谋

            else
                add(i, j + n), add(j, i + n);
    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])
            return write(0), 0;
        else if (num[i] < num[i + n])
            a[++lena] = i, ina[i] = 1;
        else
            b[++lenb] = i;
    for (rnt i = 1; i <= lena; i++)
        for (rnt j = 1; j <= lenb; j++)
            if (f[a[i]][b[j]])
                sum[a[i]]++, id[a[i]] = b[j];
    for (rnt i = 1; i <= lenb; i++)
        for (rnt j = 1; j <= lena; j++)
            if (!f[b[i]][a[j]])
                sum[b[i]]++, id[b[i]] = a[j];
    if (lena && lenb)
        ans++;
    for (rnt i = 1; i <= n; i++)
        if (sum[i] == 1 && !sum[id[i]])
            ans++;
        else if (!sum[i] && ((ina[i] && lena > 1) || (!ina[i] && lenb > 1)))
            ans++;
    write(ans);
    return 0;
}