Link

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

#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;
}