Rikka with Minimum Spanning Trees ICPC 2018 Xuzhou R

[ICPC 2018 Xuzhou R] Rikka with Minimum Spanning Trees

简单题。

题目链接： [ICPC 2018 Xuzhou R] Rikka with Minimum Spanning Trees 。

题目描述：

给一个 nn 点 mm 边的图，求最小生成树的边权和乘最小生成树个数的结果，对 109+710^9+7 取模。

给定随机的输入方式。 n,m≤105n,m\le 10^5 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
unsigned long long k1, k2;

unsigned long long xorShift128Plus() {
    unsigned long long k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= k3 << 23;
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

int n, m, u[100001], v[100001];
unsigned long long w[100001];

void gen() {
    scanf("%d%d%llu%llu", &n, &m, &k1, &k2);
    for(int i = 1; i <= m; ++i) {
        u[i] = xorShift128Plus() % n + 1;
        v[i] = xorShift128Plus() % n + 1;
        w[i] = xorShift128Plus();
    }
}

很显然图是随机的，也就是说，边权重复的概率几乎为 00 ，即，最小生成树几乎可以肯定只有一颗，所以直接求最小生成树边权和就行。

代码不放了。