如何计算一个图中有多少个有效的着色？

Question

我尝试了this SPOJ问题。

问题：

AMR10J -混合化学品

有N个瓶子，每个瓶子都有一种不同的化学物质。对于每个化学物质i，你已经确定了Ci，这意味着混合化学物质I和Ci会导致爆炸。你有K个不同的盒子。你可以用多少种方法将N种化学物质分到这些盒子里，这样同一盒子里的两种化学物质就不会同时引起爆炸？

输入

第一行输入是测试用例的数量。T测试用例紧跟在每个包含2行的测试用例之后。每个测试用例的第一行包含2个整数N和K。每个测试用例的第二行包含N个整数，第i个整数表示值Ci。这些化学品的编号是从0到N-1。

输出

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

约束条件

T <= 50

2个<= N <= 100

2 <= K <= 1000

0 <= Ci

对于所有的i，i != Ci

样本输入

3.

3 3

1 2 0

4 3

1 2 0 0

3 2

1 2 0

样本输出

6

12

0

在第一个测试用例中，我们不能混合任何两种化学物质。因此，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-难的，但是这个图有一些特殊的结构，我将在列举一些计算着色的基本属性后立即利用它。第一个观察结果是，如果图中有一个没有邻居的节点，如果我们删除该节点，着色的数量减少了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)写成一个伸缩sum：

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).

Answer 2

请注意，在删除所有平行边之后，我们最多只能有n边。这意味着在任何一个连接的组件中，我们只能看到一个循环(而且很简单)，这使得组合学变得相当简单。(循环仅取决于每个节点可以繁殖的边数，上限为1。)

第二个例子：

k = 3

       << 0 <-- 3
      /   ^
     /    ^
    1 --> 2

由于循环是自包含的，因此与一个循环的任何连接都会消除另一个循环的可能性。在上面的示例中，我们不能通过添加更多节点来创建涉及节点3的第二个周期，并且相同的问题将扩展到任何后续连接的节点。

因此，执行搜索就足够了，分离出连接的组件，并标记它们的节点计数以及它们是否包含循环。给定一个连通组件，其中节点的c是循环的一部分，而m节点不是，我们有以下公式(David Eisenstat帮助我更正了the count of colourings of a cycle的组合)：

if the component has a cycle:
  [(k - 1)^c + (-1)^c * (k - 1)] *
  (k - 1)^(m)

otherwise:
k * (k - 1)^(m - 1)

正如David Eisenstat所指出的，将所有这些结果相乘以得到最终的计数。