题目链接

题目大意

给你一个矩阵（dmy教你怎么生成），对这个矩阵进行染色，染相应的格子的代价是相应格子的权值。如果一个子矩阵的三个角被染色了，那么最后一个角可以免费染色。

例如上表，三个x的地方染色后，O处可以免费染色

求染色完整个矩阵所需要的最小花销。

解题思路

对于一个位置(i,j)，如果该格子是黑色，我们连一条A_i到B_j的边。操作不改变连通性，由此容易证明，可以全
部染黑等价于初始联通。利用 Prim 算法求解最小生成树即可。复杂度为O(n^2)。

实践证明可以使用克鲁斯卡尔算法(sort/桶)卡常飘过，感谢牛客的评测机

代码实现

#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;

const int N = 5e3+7;
const int eps = 1e-8;
const int inf = 0x7f7f7f7f;
const int mod = 1e9+7;
int T;
int n,m,k;
int A,B,C,D,P;
long long now;
struct Edge{
    int u,v,w;
    bool operator < (const Edge &o)const{
        return w < o.w;
    }
}e[N * N];
int cnt;
int fa[N*2];

int get(int x){
    return x==fa[x] ? x : fa[x]=get(fa[x]);
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n>>m;
    cin>>A>>B>>C>>D>>P;
    now=A;
    for(int i=1;i<=n+m;i++) fa[i]=i;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            now=(now*now*B+now*C+D)%P;
            e[++cnt].w=now;
            e[cnt].u=i,e[cnt].v=j+n;
        }
    }
    sort(e+1,e+n*m+1);
    long long ans=0;
    for(int i=1;i<=n*m;i++){
        int u=e[i].u,v=e[i].v,w=e[i].w;
        u=get(u);v=get(v);
        if(u==v)continue;
        fa[u]=v;
        ans+=w;
    }
    cout<<ans;
    return 0;
}