2021牛客多校3 B
题意：
给一个 n × m 的网格，每个格子有一个权值，若由 4 个格子组成的正方形中有 3 个已经染色，则第四个可免费染色 （白嫖），求染色全图所需最小代价
思路：
白嫖条件为：
假设我们白嫖
c
(
x
,
y
)
c(x,y)
c(x,y)
假设
c
(
x
+
1
,
y
+
1
)
,
c
(
x
+
1
,
y
)
,
c
(
x
,
y
+
1
)
c(x+1,y+1),c(x+1,y),c(x,y+1)
c(x+1,y+1),c(x+1,y),c(x,y+1) 已被染色
极其巧妙地建图：
将所有格子的横纵坐标分别提出来，横坐标组成一张图，纵坐标组成一场图，格子 c(i, j) 代表连接 i，j 这两个顶点的一条边
按照上述建图方式，可以发现 （这谁想得到）：
x
,
x
+
1
,
y
,
y
+
1
x,x+1,y,y+1
x,x+1,y,y+1 及其连边组成的图中，如果互相连通，则代表这四个点都被染色，想要互相连通且代价最小，即求最小生成树。稠密图选用prim （但是好多队都用 Kruskal 过了），注意细节即可。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<math.h>
#include<queue>
using namespace std;
typedef long long ll;
typedef double dd;
typedef pair<int, int> pii;
typedef pair<dd, dd> pdd;
const int MAXN = 25000010;
const int MAXM = 6010;
const int inf = 1e9 + 7;
const dd eps = 1e-5;
int dis[10010];
bool vis[10010];
int b, c, d, n, m, p;
int mp[10010][10010]; //选用邻接表存图+堆优化会 MLE
ll a;
int sum;
void prim()
{
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
for (int k = 1;k <= n + m;k++)
{
int x = 0;
for (int j = 1;j <= n + m;j++)
{
if (!vis[j] && dis[j] < dis[x])
{
x = j;
}
}
vis[x] = 1;
sum += dis[x];
for (int j = 1;j <= n + m;j++)
{
if (!vis[j] && dis[j] > mp[x][j])
{
dis[j] = mp[x][j];
}
}
}
}
int main()
{
cin >> n >> m >> a >> b >> c >> d >> p;
memset(mp, 0x3f, sizeof(mp));
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
{
a = (a * a * b + a * c + d) % p;
mp[i][j + n] = mp[j + n][i] = a;//此处相当于两张图因此连 i 和 j+n 两点
}
}
prim();
printf("%d", sum);
}