• 周一. 8月 15th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

2021牛客多校第三场 B题

admin

11月 28, 2021

这道题当时很快就发现了要取n+m-1个,以及和行列有关,只能说太久没打了,思维退化,没有关联到2分图后n+m个点取最小生成树

正解:根据上面想到的那两个性质,我们不妨把矩阵的行列分成二分图的两边点,然后将矩阵中的数作为边及边权,这样就构成了一张二分图,然后用最小生成树保证连通性,只要2分图联通,那么一定可以通过行列将所有点都染黑

注意:这道题用要用prim,kruskal算法最后一个点会因为边数很大被卡常

下附代码:

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 int flag[20005];
 5 ll dis[20005];
 6 ll edge[5005][5005];
 7 ll a[25005005];
 8 ll n,m,A,b,c,d,p;
 9 const ll INF=0X3f3f3f3f3f3f3f3f;
10 struct node{
11     ll x,l;
12     friend bool operator < (struct node a,struct node b){
13         return a.l>b.l;
14     }
15 };
16 int main(){
17     priority_queue<node> q;
18     scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&m,&A,&b,&c,&d,&p);
19     a[0]=A;
20     for (int i=1; i<=n*m; i++){
21         a[i]=(b*a[i-1]*a[i-1]+c*a[i-1]+d)%p;
22     }
23     for (int i=1; i<=n; i++){
24         for (int j=1; j<=m; j++){
25             edge[i][j]=a[(i-1)*m+j];
26         }
27     }
28     ll res=0;
29     for (int i=1; i<=n+m; i++) dis[i]=INF;
30     dis[1]=0;
31     q.push({1,0});
32     memset(flag,0,sizeof(flag));
33     while (!q.empty()){
34         node x=q.top();
35         q.pop();
36         int now=x.x;
37         if (flag[now]==1) continue;
38         flag[now]=1;
39       //  printf("%d %d
",dis[now],now);
40         res+=dis[now];
41         if (now<=n){
42             for (ll i=1; i<=m; i++){
43                 if (!flag[i+n] && dis[i+n]>edge[now][i]){
44                     dis[i+n]=edge[now][i];
45                     q.push({i+n,dis[i+n]});
46                 }
47             }
48         }
49         else {
50             for (ll i=1; i<=n; i++){
51                 if (!flag[i] && dis[i]>edge[i][now-n]){
52                     dis[i]=edge[i][now-n];
53                     q.push({i,dis[i]});
54                 }
55             }
56         }
57     }
58     printf("%lld",res);
59 }

View Code

发表回复

您的电子邮箱地址不会被公开。