2021牛客多校3 B

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);
}
上一篇:2021-07-28


下一篇:CSUST 黄金矿工 题解(分组背包+转换dp方程状态)