DDOSvoid's Blog

Luogu P3513 [POI2011] KON-Conspiracy

发表于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P3513

简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，求有多少种划分方案可以将这 $n$ 个点划分成两个集合 $S,T$，满足 $|S|,|T|\ge 1$ 且 $S$ 是一个团，$T$ 是一个独立集

$n\le 5000,m\le \frac{n\times (n-1)}{2}$

Solution

我们考虑 $2-sat$，$0$ 表示将划分到 $S$，$1$ 表示划分到 $T$，如果 $(u,v)$ 之间有边，那么我们有 $u\rightarrow v’,v\rightarrow u’$，如果 $(u,v)$ 之间无边，那么我们有 $u’\rightarrow v,v’\rightarrow u$，然后我们利用 $2-sat$ 可以求出一个解

然后我们考虑如何计数，仔细思考可以发现，解的数量是 $O(n^2)$ 范围，且我们可以利用一个解去推出其他解，具体的做法是我们对于已经求出来的一个解，尝试将一个点从 $S$ 移入 $T$，或者将一个点从 $T$ 移入 $S$，或者交换 $S$ 和 $T$ 的一个点，需要注意如果一开始求出来的解不满足 $S$ 和 $T$ 都非空答案要减 $1$

时间复杂度 $O(n^2)$

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
#include <iostream>
#include <vector>
#include <stack>
#define maxn 10010
using namespace std;

int n;

struct Edge {
    int next, to; 
} e[25000010]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int dfn[maxn], low[maxn], bl[maxn], scc; bool ins[maxn]; stack<int> S;
void tarjan(int u) {
    static int cnt = 0; 
    dfn[u] = low[u] = ++cnt; ins[u] = 1; S.push(u);
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        int t; ++scc;
        do {
            t = S.top(), S.pop();
            bl[t] = scc, ins[t] = 0; 
        } while (t != u); 
    }
}

int main() { fill(head, head + maxn, -1);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; vector g(n + 1, vector<bool>(n + 1));
    for (int i = 1; i <= n; ++i) {
        int x, l; cin >> l;
        for (int j = 1; j <= l; ++j) cin >> x, g[i][x] = 1;
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j < i; ++j) { 
            if (g[i][j]) add_edge(i + n, j), add_edge(j + n, i);
            else add_edge(i, j + n), add_edge(j, i + n);
        }
    for (int i = 1; i <= 2 * n; ++i) if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= n; ++i)
        if (bl[i] == bl[i + n]) return cout << 0 << "\n", 0;
    vector<int> t1, t2; 
    for (int i = 1; i <= n; ++i)
        if (bl[i] < bl[i + n]) t1.push_back(i);
        else t2.push_back(i);
    int ans = t1.size() > 0 && t2.size() > 0;
    vector<int> e1(n + 1), e2(n + 1);
    for (auto u : t1)
        for (int v = 1; v <= n; ++v)
            if (g[u][v]) ++e1[v];
    for (auto u : t2)
        for (int v = 1; v <= n; ++v)
            if (g[u][v]) ++e2[v];
    for (auto u : t1)
        if (!e2[u] && t1.size() > 1) ++ans;
    for (auto u : t2)
        if (e1[u] == t1.size() && t2.size() > 1) ++ans;
    for (auto u : t1)
        for (auto v : t2) {
            if (g[u][v]) --e1[v], --e2[u];
            if (!e2[u] && e1[v] == t1.size() - 1) ++ans;
            if (g[u][v]) ++e1[v], ++e2[u];
        }
    cout << ans << "\n";
    return 0;
}