c++ - 如何计算图表中有多少有效颜色?
问题描述
我尝试了这个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
解释在第一个测试用例中,我们不能混合任何两种化学品。因此,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;
}
解决方案
在一般图表中计算颜色的数量是#P-hard,但是这个图表有一些特殊的结构,我将在一分钟内列举一些颜色计数的基本属性后加以利用。第一个观察结果是,如果图有一个没有邻居的节点,如果我们删除该节点,着色的数量会减少 k 倍。第二个观察是,如果一个节点只有一个邻居并且我们删除它,着色的数量会减少 k-1 倍。第三是着色数等于每个连通分量的着色数的乘积。第四个是我们可以删除除一条平行边之外的所有边。
使用这些属性,为该图的 2 核的每个连通分量确定一个公式就足够了,这是一个具有一定长度的简单循环。令 P(n) 和 C(n) 分别为具有 n 个节点的路径或循环着色的方式数。我们使用上面的基本属性来查找
P(n) = k (k-1)^(n-1).
我认为找到 C(n) 的公式需要删除收缩公式,这会导致重复
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).
推荐阅读
- python - BeautifulSoup Amazon Web Scraping - NoneType 错误
- javascript - 如何在 Discord.js 中使用超时
- python-3.x - 在pythonista中添加小数时如何防止计算错误?
- testing - 手风琴未通过可访问性检查
- react-native - 如何构建完全在智能合约上运行的移动应用程序?
- java - JavaFx 将输入控件标记为强制
- python - 在 Pandas 中使用整数有效地切片非整数多级索引
- python - 使用 Python 的 asyncio.Semaphore 控制 HTTP 请求的并发性
- javascript - 我将如何创建这个跳转页面?
- python - Tkinter回调Python IndexError中的Tkinter异常:列表索引超出范围