ARC093C Bichrome Spanning Tree

tony102

2021 年 10 月 08 日

1310 次浏览

暂无评论

1105字数

题解

[Link](https://atcoder.jp/contests/arc093/tasks/arc093_c)

## Sol

首先应该想到一件事情，就是应该对原图的 MST 与给定的 $x$ 进行比较，分类讨论做。

为什么要这么想？我们来构造一种合法的染色方案，设 $mst$ 为原图的 MST 大小，假设 $mst < x$ ，要构造异色的大小为 $x$ 的生成树，我们可以让 $mst$ 中的边全部染一种颜色（假设为白色），其余的边全部染成黑色，这样只需要再最后给方案数乘 $2$ 即可。若 $mst > x$ ，显然没有合法方案。

继续考虑 $mst < x$ 的怎么做。假设我们强制选了第 $i$ 条边，这时的 MST 大小为 $m_i$ 。再次分类讨论：

1. 若 $m_i < x$ ，那么第 $i$ 条边也是可以加进最小生成树的一条边，那么它也需要染成白色。
2. 若 $m_i > x$ ，对结果没有影响。
3. 若 $m_i = x$ ，记已经强制染色的边的边数为 $cnt$ ，初始时因为 MST 已经有 $n-1$ 条边被强制染白色了，所以 $cnt = n - 1$。对于第 $i$ 条边，若染成黑色，其余边随便染，则对答案贡献为：$2^{m-cnt-1}$，再强制染成白色，$cnt \to cnt + 1$

若一开始求出的 $mst = x$，就可以先强制这棵 MST 异色， 方案数为： $(2^{n - 1} - 2) \times 2^{m-n+1}$，再强制染成白色。接着按照 $mst < x$ 的做即可。

## Code

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 2e3 + 5;
const int mod = 1e9 + 7;

int n, m, x, num;
int fa[SIZE], msti[SIZE], pw[SIZE];

struct node {
	int from, to, v;
	inline bool operator < (const node &a) const {
		return v < a.v;
	}
} edge[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

int qPow(int a, int b) {
	int ans = 1ll;
	for ( ; b; b >>= 1, a = a * a % mod) {
		if (b & 1) ans = ans * a % mod;
	}
	return ans % mod;
}

int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void init() {
	for (int i = 1; i <= n; ++ i) fa[i] = i;
}

int kruskal(int tot = 0) {
	int val = 0;
	for (int i = 1; i <= m; ++ i) {
		int u = find(edge[i].from), v = find(edge[i].to);
		if (u != v) ++ tot, val += edge[i].v, fa[v] = u;
		if (tot == n - 1) break;
	}
	return val;
}

signed main() {
	n = read(), m = read(), x = read();
	for (int i = 1; i <= m; ++ i) {
		edge[i].from = read(), edge[i].to = read(), edge[i].v = read();
	}
	const int N = std::max(n, m); pw[0] = 1ll;
	for (int i = 1; i <= N; ++ i) pw[i] = pw[i - 1] * 2ll % mod;
	init();
	std::sort(edge + 1, edge + m + 1);
	int mst = kruskal(), ans = 0;
	if (mst > x) return puts("0"), 0;
	else if (mst == x) ans = (pw[n - 1] - 2ll + mod) % mod * pw[m - n + 1] % mod;
	for (int i = 1; i <= m; ++ i) {
		init(); fa[edge[i].from] = fa[edge[i].to];
		msti[i] = kruskal(1) + edge[i].v;
	}
	std::sort(msti + 1, msti + m + 1);
	for (int i = n; i <= m; ++ i) {
		if (msti[i] == x) ans = (ans + pw[m - i + 1]) % mod;
	}
	printf("%lld\n", ans % mod);
	return 0;
}
```

最后修改：2021 年 10 月 08 日