2021牛客暑期多校训练营3

B. Black and white

题意：

​ 给一个矩阵，根据游戏规则去涂色，让求最小权值和。

复盘：

​ 要求权值和最小，即使要涂色的格子数最小，根据规则较容易推出对于 n*m 的矩阵，需要 n+m-1 格子涂色，分别是每行对应一个格子，每列对应一个格子，减去重复的一个（例如：将第一列和第一行先涂色，n+m-1 个格子，那么剩下格子都会免费被涂色）

​ 比赛时推出 n+m-1 这个结论就十分happy，直接去打了一个先遍历选出每一行的最小值（并打上标记），再在剩下的遍历去找每一列的最小值，sum 求和，感觉十分完美，每一行一个，每一列一个，没什么毛病，样例也过了，一交WA了？？？

​ 然后苦思冥想，总算想明白哪里出问题了，先行…再列，这还能有先后？？？把问题局部化了，行和列是一个整体的，不能分先后，然后我就懵逼了，一直念叨着“每一行一个，每一列一个”，就是不知道如何下去了

​ 比赛结束后，一看大佬代码，这怎么还用上了并查集，这怎么这么像最小生成树，看完…这就是最小生成树，想了好一会，内心只有：太强了，太妙了，是我无法想到的，orz

​ 为什么是最小生成树，我们考虑任意两行两列所成的四个坐标，若已经出现了三个坐标，则第四个就不需要了。现在考虑如何判断新加入点是否需要，即它不会由之前的坐标推出来。

​ 三点满足条件的点会确定一个矩阵，因为三个点就能确定两行两列，再根据题目一行一点，一列一点，不如将行列看成点，现将两行点和两列点放在同一个连通块里，第四个坐标放进来，行坐标和列坐标连通，即不需要，用并查集维护，再根据边权从小到大去跑最小生成树即可

​ n+m个点，n+m-1条边，从点边的关系也可看成最小生成树，可比赛时没有看出

反思：

​ 比赛时，推到了三个点会确定第四个点，想着打爆力将能确定的点丢弃掉，N3次，不知如何优化了，没有转换到点（将行列看成点，这也没想到）之间连通性问题。

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

const int N = 5005;
int f[N*2]; 
int fd(int k) 
{ 
    return f[k] == k ? k : f[k] = fd(f[k]); 
}
vector < pair <int, int> > e[100005]; 
signed main()
{
    int n,m,a,b,c,d,p;
    cin>>n>>m>>a>>b>>c>>d>>p;
    int tot=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            a = (a*a*b + a*c + d)%p;
            e[a].push_back(make_pair(i, n+j));
        }
    }
    for(int i=1;i<=n+m;i++) f[i] = i;
    int ans=0, cnt=0;
    for(int i=0;i<p;i++)
    {
        for(int j=0;j<e[i].size();j++)
        {
            int x = fd(e[i][j].first), y = fd(e[i][j].second);
            if(x != y)
            {
                cnt++;
                f[y] = x;
                ans += i;
            }
        }
        if(cnt == n+m-1) break ;
    }
    cout<<ans<<endl;

    return 0;
}