Link
给定一个 n 个点 m 条边的简单无向连通图，其中图的前 n−1 条边构成了图的一棵生成树。
你需要为每条边分配一个范围在 [1,m] 的权值，且每种权值只能用一次。
定义一种分配方案的得分是这个图的最小生成树的权值和。
求所有可能的分配方案中，前 n−1 条边是图的最小生成树的方案的得分和，对 109+7 取模。
2≤n≤20,n−1≤m≤n(n−1)2。
n 很小，不由得联想到与 2n 有关的做法。
考虑类似 Kruskal 的做法，按照 1∼m 的顺序，给每条边赋上权值。
那权值 i 可以赋给某条边，当且仅当这条边连接的两个点已经处于同一个联通块中。
结合以上的所有想法，考虑设 fi,S 表示正在分配权值 i，编号为 1∼n−1 的边中，状态 S 已经被分配最终的分配方案数，gi,S 表示答案。
那么转移无非就是把 i 分配给编号为 1∼n−1 中的边，或者是其他的边两种。
也即 fi,S→fi+1,S/fi+1,S|j。
第二种直接转移就好，第一种需要考虑可以选择哪些边，这里显然可以使用并查集预处理出 cntS，表示如果已经分配了状态 S，有哪些边可以被选。
g 的转移同理，在第二种转移时多乘一个权值即可。
剩下要做的就只有把 f 和 g 滚动一下了，时间复杂度 O(mn2n)，加点剪枝卡卡常就过了。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| #include <iostream>
#include <cstdlib>
#include <cstdio>
#define ll long long
using namespace std;
inline int read()
{
int f = 1, x = 0;
char ch;
do{
ch = getchar();
if (ch == '-')
f = -1;
}while(ch < '0' || ch > '9');
do{
x = x * 10 + ch - '0';
ch = getchar();
}while(ch >= '0' && ch <= '9');
return f * x;
}
const int N = 20;
const int mod = 1e9 + 7;
int n, m;
struct Edge {
int from, to;
} edge[N * N + 1];
ll f[1 << N], g[1 << N];
int cnt[1 << N];
namespace dsu
{
int fa[N + 1], sz[N + 1];
inline void init()
{
for (int i = 1; i <= n; i++) {
fa[i] = i;
sz[i] = 1;
}
return;
}
inline int gfa(int x)
{
if (fa[x] != x)
fa[x] = gfa(fa[x]);
return fa[x];
}
inline void update()
{
for (int i = 1; i <= n; i++)
fa[i] = gfa(i);
return;
}
inline void merge(int x, int y)
{
x = gfa(x);
y = gfa(y);
if (x != y) {
if (sz[x] < sz[y])
swap(x, y);
fa[y] = x;
sz[x] += sz[y];
}
return;
}
}
inline void dp()
{
for (int S = 0; S < 1 << (n - 1); S++) {
dsu::init();
for (int i = 1; i <= n - 1; i++)
if (S & (1 << (i - 1))) {
dsu::merge(edge[i].from, edge[i].to);
cnt[S]++;
}
dsu::update();
for (int i = n; i <= m; i++)
if (dsu::fa[edge[i].from] == dsu::fa[edge[i].to])
cnt[S]++;
}
f[0] = 1;
for (int i = 1; i <= m; i++) {
for (int S = (1 << (n - 1)) - 1; S >= 0; S--) {
f[S] %= mod;
g[S] %= mod;
if (!f[S])
continue;
for (int j = 1; j <= n - 1; j++) {
if (S & (1 << (j - 1)))
continue;
f[S | (1 << (j - 1))] += f[S];
g[S | (1 << (j - 1))] += g[S] + i * f[S];
}
f[S] = f[S] * (cnt[S] - i + 1);
g[S] = g[S] * (cnt[S] - i + 1);
}
}
return;
}
int main()
{
n = read();
m = read();
for (int i = 1; i <= m; i++)
edge[i] = { read(), read() };
dp();
printf("%d\n", g[(1 << (n - 1)) - 1] % mod);
return 0;
}
|