2021牛客多校3 B Black and white

题目描述

https://ac.nowcoder.com/acm/contest/11254/B

Solution

对于一个位置 $(x,y)$，我们连一条 $x$ 到 $y+n$ 的边，容易发现操作不会影响连通性

那么我们最终的目标就是将图连通，显然就是求一棵最小生成树

#include <iostream>
#include <vector>
#include <algorithm>
#define maxn 5010
#define ll long long
#define INF 1000000000
using namespace std;

int n, m;

ll _a, _b, _c, _d, p;

int A[maxn * maxn];

int fa[maxn * 2];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } 

struct Edge {
    int fr, to, w;

    friend bool operator < (const Edge &u, const Edge &v) { return u.w < v.w; }
} e[maxn * maxn]; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> _a >> _b >> _c >> _d >> p;
    A[0] = _a;
    for (int i = 1; i <= n * m; ++i) A[i] = (_b * A[i - 1] * A[i - 1] + A[i - 1] * _c + _d) % p;
    for (int i = 1, cnt = 0; i <= n; ++i)
        for (int j = 1; j <= m; ++j) ++cnt, e[cnt] = { i, j + n, A[cnt] };
    sort(e + 1, e + n * m + 1); init_fa(n + m); ll ans = 0; 
    for (int i = 1; i <= n * m; ++i) {
        int u = e[i].fr, v = e[i].to, w = e[i].w, fu, fv;
        if ((fu = find(u)) == (fv = find(v))) continue;
        fa[fu] = fv; ans += w; 
    } cout << ans << "\n"; 
    return 0;
}