链接
https://ac.nowcoder.com/acm/contest/11254/B
题意
$n*m$ 的方格中，初始时每格都是白色，每格都有一个权值，代表染成黑色的花费。
任意两行与任意两列的交集为四个格子，若其中三个格子已经染成黑色，那么剩下那个可以免费染成黑色。
求把所有格子染成黑色的最小花费。
思路
将题意转化为图论问题，将行列作为二分图的两个集合，把一个格子染成黑就是行与列连线，最终形成一张完全二分图。
而在其中某些边可以是免费的，我们要求的是最小的边权和。
可以发现免费的边具有传递性，即当我们满足要求可以连一条免费的边后，可能会有更多的边可以免费连。
如果有两行两列连通时，即最少需要三条需要花费的边，涂黑三个格子，那么就可以免费涂一个格子。
易发现这时在当前连通块中再加入一个点，这条边是需要花费的，然后就可以添加免费边使当前联通块中行列形成完全二分图。
不断往连通块里加点，最终使整张图连通，那么容易得到最小花费就是最小生成树。
代码
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
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
int fa[10005];
VPII e[100005];
int find(int x) {
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,a,b,c,d,p;cin>>n>>m>>a>>b>>c>>d>>p;
for(int i=1,pre=0,now=a;i<=n;i++) {
for(int j=1;j<=m;j++) {
int x=m*(i-1)+j;
pre=now;
now=(1ll*pre*pre*b%p+1ll*pre*c%p+d)%p;
e[now].EB(i,n+j);
}
}
for(int i=1;i<=n+m;i++) fa[i]=i;
int res=0,cnt=n+m-1;
for(int i=0;i<p;i++) {
for(auto x:e[i]) {
int fu=find(x.FI),fv=find(x.SE);
if(fu==fv) continue;
fa[fu]=fv;
res+=i;
--cnt;
if(!cnt) break;
}
}
cout<<res<<'\n';
return 0;
}
|