题目大意

给定一个矩阵cc，初始每个格子都是白色的，可以花费c[i][j]c[i][j]的代价将i,ji,j位置染成黑色，特殊的，如果行i,ji,j和行k,hk,h满足mat[i][k],mat[i][h],mat[j][k]mat[i][k],mat[i][h],mat[j][k]都是黑色，那么mat[j][h]mat[j][h]可以消耗00的代价直接染成黑色。求将整个矩阵染黑的最小花费。

思路

这道题在赛中就有了考虑，保证每行每列都有一个黑色，然后在任何一个其他地方安放一个黑色即可将所有位置涂黑，也想了一些方法来做这道题，但是都没有过去，赛后看了题解才恍然大悟。

正如赛中的考虑，将每行抽象成一个点，编号 [1,n][1,n]，将每列抽象成一个点，编号 [n+1,n+m][n+1,n+m]，对于 mat[i][j]mat[i][j] 涂黑可以定义为在 i,n+ji,n+j 点之间连接一条边，那么整个题目就可以抽象成一个二分图，正如赛中的考虑，每行每列有一个，加上其他地方安放一个，就是保证了二分图的连通性。显然，当二分图联通的时候，可以无消耗地染色整个矩阵。

之后就是在二分图上求最小生成树即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mat[5005][5005];
bool vis[10005];
int dis[10005];
int main()
{
	int n, m;
	ll a, b, c, d, p;
	cin >> n >> m >> a >> b >> c >> d >> p;
	int len = n * m + 1;
	ll cal = a;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			cal = mat[i][j] = (cal * cal * b + cal * c + d) % p;
	}
	int cur = 1;
	vis[cur] = true;
	dis[cur] = 0;
	memset(dis, 0x3f, sizeof(dis));
	for (int i = 1; i <= m; i++)
	{
		dis[n + i] = min(dis[n + i], mat[cur][i]);
	}
	int ans = 0;
	while (1)
	{
		int tmp = -1;
		int MIN = 0x7fffffff;
		for (int i = 1; i <= m + n; i++)
		{
			if (!vis[i] && dis[i] < MIN)
			{
				MIN = dis[i];
				tmp = i;
			}
		}
		if (tmp == -1)break;
		ans += MIN;
		vis[tmp] = true;
		if (tmp <= n)
		{
			for (int i = 1; i <= m; i++)
			{
				dis[n + i] = min(dis[n + i], mat[tmp][i]);
			}
		}
		else
		{
			for (int i = 1; i <= n; i++)
			{
				dis[i] = min(dis[i], mat[i][tmp - n]);
			}
		}
	}
	cout << ans << endl;
	return 0;
}
/*
2 2
5 1
5 1
4 4
2 4 0 3
3 0 3 3
0 0 3 3
3 5 0 0
2 8
1 2 3 4 7

2 5
0 0 0 0 1
1 1 1 1 0

*/