题解 | #Black and white#

B题题解

队友别骂了，别骂了，我不该以为这题是最短路

思路

为了实现最少花费，需满足：在我们涂完若干个点后，其他的点对总花费不再有贡献（涂黑这些点时不花钱了）
我们会发现 ：最少，我们需要涂黑 n + m - 1 个点，且涂完这些点后 所有的行 和所有的列 会都在一个联通块里面

举例 如下：
不妨令 n = 2，m = 2，此时我们最少需要涂 3个点
令 g[1][1] = g[1][2] = g[2][1] = 1，g[2][2] = 3
为了最少花费，我们要涂的三个点显然是：(1,1)，(1,2)，(2,1)
涂完(1,1)后，我们把 行1 和 列1 放到一个联通块里面
涂完(1,2)后，我们把 行1 和 列2 放到一个联通块里面
涂完(2,1)后，我们把 行2 和 列1 放到一个联通块里面
到此，所有的行 和 所有的列 都在一个联通块里了，同时我们也实现了最少花费

在这个例子中，涂黑任意三个点都可以实现 把所有的行 和 所有的列 都放在一个联通块里
但为了 最少花费，所以我们选择的是 (1,1)，(1,2)，(2,1) 这三个点
我们提炼出两个关键字 联通块、最小花费：连通块（并查集）+ 最小花费 = Kruskal(最小生成树)

所以该题使用 Kruskal 求最小(花费)生成树

Code如下

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 3e7+10;
const int M = 5010;

struct node{
    int x,y;
    ll v;
    bool operator < (const node & u) const { return v < u.v; }
}A[N];
int fa[2*M];
int n,m,a,b,c,d,p;

void Init(){
    A[0].v=a; 
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)  {
        int id=m*(i-1)+j;
        A[id]={i,j,((ll)A[id-1].v*A[id-1].v*b+(ll)A[id-1].v*c+d)%p};
    }
}

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

void kruskal(){
    //选若干个点（最少n+m-1个）,使得所有行，所有列在一个联通块里面
    ll res=0,cnt=n+m-1;
    for(int i=1;i<=n+m;i++) fa[i]=i; // 1~n 表示行，n+1~n+m 表示列

    sort(A+1,A+1+m*n);
    for(int i=1;i<=m*n;i++){
        int x=A[i].x,y=A[i].y,v=A[i].v;
        x=find(x),y=find(n+y);
        if(!cnt) break;  
     // 按理说 没有 cnt 这个变量 应该也可以，但是去掉后 只能过90% 剩下的10% 会 T，不知道为啥
        if(x!=y){    
            fa[x]=y;
            res+=v;
            cnt--;
        }
    }
    cout<<res<<endl;
}

int main(){
    cin>>n>>m>>a>>b>>c>>d>>p;
    Init();
    kruskal();
    return 0;
}