A. Rikka with Minimum Spanning Trees

Link

Solution

2018年ACM-ICPC徐州区域赛A题，神仙签到放倒一片，结果非常惨烈，其实按题意建图后跑一遍最小生成树即可。

Code

#include <algorithm>
#include <cmath>
#include <map>
#include <iostream>
#include <vector>
#define mpr make_pair
typedef unsigned long long ULL;
const int MOD = 1e9 + 7;
using namespace std;

ULL n, m, k1, k2;
int fa[100001];
vector<pair<pair<int, int>, ULL>>Edges;

ULL get() {
    ULL k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= k3 << 23;
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

void gen() {
    cin >> n >> m >> k1 >> k2;
    Edges.clear();
    for (int i = 1; i <= m; i++) {
        int u = get() % n + 1;
        int v = get() % n + 1;
        ULL w = get();
        Edges.push_back(mpr(mpr(u, v), w));
    }
}

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

int findr(int x) {
    if (x == fa[x])return x;
    else return fa[x] = findr(fa[x]);
}

void merge(int x, int y) {
    int xr = findr(x);
    int yr = findr(y);
    if (xr != yr)fa[xr] = yr;
}

bool cmp(pair<pair<int, int>, ULL> a, pair<pair<int, int>, ULL> b) {
    return a.second < b.second;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        gen();
        init();
        sort(Edges.begin(), Edges.end(), cmp);
        int cnt = 0, ans = 0;
        for (auto e : Edges) {
            int u = e.first.first, v = e.first.second;
            if (findr(u) != findr(v)) {
                merge(u, v);
                ans = (ans + e.second) % MOD;
                cnt++;
            }
        }
        if (cnt != n - 1)cout << 0 << endl;
        else cout << ans % MOD << endl;
    }
    return 0;
}