c++ - 如何计算图中有多少种有效着色？

Question

我尝试了 this SPOJ问题。

问题:

AMR10J - 混合化学品

有 N 个瓶子，每个瓶子都有不同的化学品。对于每种化学品 i，您已确定 C[i]，这意味着混合化学品 i 和 C[i] 会导致爆炸。你有 K 个不同的盒子。你有多少种方法可以将 N 种化学物质分成这些盒子，使得同一个盒子中的两种化学物质不会一起引起爆炸？

输入

输入的第一行是测试用例的个数T。接下来的T个测试用例每行包含2行。 每个测试用例的第一行包含 2 个整数 N 和 K。 每个测试用例的第二行包含 N 个整数，第 i 个整数表示值 C[i]。这些化学品从 0 到 N-1 编号。

输出

对于每个测试用例，输出以 1,000,000,007 为模的方式数。

约束

T <= 50

2 <= N <= 100

2 <= K <= 1000

0 <= C[i] < N

对于所有 i, i != C[i]

样本输入

3

3 3

1 2 0

4 3

1 2 0 0

3 2

1 2 0

样本输出

6

12

0

解释 在第一个测试用例中，我们不能混合任何 2 种化学品。因此，3 个盒子中的每一个都必须包含 1 种化学物质，这导致总共有 6 种方式。 在第三个测试用例中，我们无法将 3 种化学品放入满足所有 3 个条件的 2 个盒子中。

问题总结，给定一组化学品和一组盒子，计算有多少种可能的方法将这些化学品放在盒子里，这样化学品就不会爆炸。 起初我用蛮力法来解决这个问题，我递归地将化学物质放入盒子中并计算有效配置，我第一次尝试就得到了 TLE。

后来才知道可以用图形着色来解决这个问题。 我可以将化学物质表示为顶点，如果它们不能彼此放置，则化学物质之间会有一条边。 这组框可以用作顶点颜色，我需要做的就是计算图形有多少种不同的有效着色。 我应用这个概念来解决问题，不幸的是我又得了 TLE。我不知道如何改进我的代码，我需要帮助。

代码:

#include <bits/stdc++.h>

#define MAXN 100

using namespace std;

const int mod = (int) 1e9 + 7;

int n;
int k;

int ways;

void greedy_coloring(vector<int> adj[], int color[])
{
    int u = 0;

    for (; u < n; ++u)
        if (color[u] == -1)//found first uncolored vertex
            break;

    if (u == n)//no uncolored vertexex means all vertexes are colored
    {
        ways = (ways + 1) % mod;
        return;
    }

    bool available[k];

    memset(available, true, sizeof(available));

    for (int v : adj[u])
        if (color[v] != -1)//if the adjacent vertex colored, make its color unavailable
            available[color[v]] = false;

    for (int c = 0; c < k; ++c)
        if (available[c])
        {
            color[u] = c;

            greedy_coloring(adj, color);

            color[u] = -1;//don't forgot to reset the color
        }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;

    cin >> T;

    while (T--)
    {
        cin >> n >> k;

        vector<int> adj[n];

        int c[n];

        for (int i = 0; i < n; ++i)
        {
            cin >> c[i];

            adj[i].push_back(c[i]);
            adj[c[i]].push_back(i);
        }

        ways = 0;

        int color[n];

        memset(color, -1, sizeof(color));

        greedy_coloring(adj, color);

        cout << ways << "\n";
    }

    return 0;
}

Answer 1

计算一般图中的着色数量是#P-hard，但是这个图有一些特殊的结构，我将在列举着色计数的一些基本属性后利用它。第一个观察是，如果图中有一个没有邻居的节点，如果我们删除该节点，着色的数量会减少 k 倍。第二个观察是，如果一个节点只有一个邻居并且我们删除它，着色的数量会减少 k-1 倍。第三个是着色数等于每个连通分量的着色数的乘积。第四个是我们可以删除除一条平行边之外的所有边。

使用这些属性，足以为该图的 2 核的每个连通分量确定一个公式，这是一个具有一定长度的简单循环。设 P(n) 和 C(n) 分别是用 n 个节点为路径或循环着色的方法数。我们使用上面的基本属性来查找

P(n) = k (k-1)^(n-1).

我认为找到 C(n) 的公式需要 deletion contraction formula , 导致复发

C(3) = k (k-1) (k-2), i.e., three nodes of different colors;
C(n) = P(n) - C(n-1) = k (k-1)^(n-1) - C(n-1).

将上述递归乘以 (-1)^n。

(-1)^3 C(3) = -k (k-1) (k-2)
(-1)^n C(n) = (-1)^n k (k-1)^(n-1) - (-1)^n C(n-1)
            = (-1)^n k (k-1)^(n-1) + (-1)^(n-1) C(n-1)
(-1)^n C(n) - (-1)^(n-1) C(n-1) = (-1)^n k (k-1)^(n-1)

设 D(n) = (-1)^n C(n)。

D(3) = -k (k-1) (k-2)
D(n) - D(n-1) = (-1)^n k (k-1)^(n-1)

现在我们可以将 D(n) 写成伸缩和:

D(n) = [sum_{i=4}^n (D(n) - D(n-1))] + D(3)
D(n) = [sum_{i=4}^n (-1)^n k (k-1)^(n-1)] - k (k-1) (k-2).

将其分解为两个几何和，然后很好地抵消。

D(n) = [sum_{i=4}^n (-1)^n ((k-1) + 1) (k-1)^(n-1)] - k (k-1) (k-2)
     = sum_{i=4}^n (1-k)^n - sum_{i=4}^n (1-k)^(n-1) - k (k-1) (k-2)
     = (1-k)^n - (1-k)^3 - k (k-1) (k-2)
     = (1-k)^n - (1 - 3k + 3k^2 - k^3) - (2k - 3k^2 + k^3)
     = (1-k)^n - (1-k)
C(n) = (-1)^n (1-k)^n - (-1)^n (1-k)
     = (k-1)^n + (-1)^n (k-1).