Sol
首先应该想到一件事情,就是应该对原图的 MST 与给定的 $x$ 进行比较,分类讨论做。
为什么要这么想?我们来构造一种合法的染色方案,设 $mst$ 为原图的 MST 大小,假设 $mst < x$ ,要构造异色的大小为 $x$ 的生成树,我们可以让 $mst$ 中的边全部染一种颜色(假设为白色),其余的边全部染成黑色,这样只需要再最后给方案数乘 $2$ 即可。若 $mst > x$ ,显然没有合法方案。
继续考虑 $mst < x$ 的怎么做。假设我们强制选了第 $i$ 条边,这时的 MST 大小为 $m_i$ 。再次分类讨论:
- 若 $m_i < x$ ,那么第 $i$ 条边也是可以加进最小生成树的一条边,那么它也需要染成白色。
- 若 $m_i > x$ ,对结果没有影响。
- 若 $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
#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;
}