这道题当时很快就发现了要取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 }