Cave Escape

The first line of the input gives the numbers of test cases, $\mathbf{T}$ . $\mathbf{T}$ test cases follow.
Each test case contains two lines.
The first line contains six integers $\mathbf{N}$ , $\mathbf{M}$ , $\mathbf{S_R}$ , $\mathbf{S_C}$ , $\mathbf{T_R}$ and $\mathbf{T_C}$ as described above.
The next line contains fix integers in the following format, respectively:
$\mathbf{X_1}$ $\mathbf{X_2}$ $\mathbf{A}$ $\mathbf{B}$ $\mathbf{C}$ $\mathbf{P}$
These values are used to generate $\mathbf{V_{ij}}$ as follows:
We define:
$\mathbf{X_i} = (\mathbf{A} \times \mathbf{X_{i-1}} + \mathbf{B} \times \mathbf{X_{i-2}} + \mathbf{C})\ module\ \mathbf{P}$ , for i = 3 to $\mathbf{N} \times \mathbf{M}$ .
We also define:
$\mathbf{V_{ij}} = \mathbf{X_{(i-1)*M+j}}$ , for ${i=1}$ to $\mathbf{N}$ , and ${j=1}$ to $\mathbf{M}$ .
$1 \leq \mathbf{T} \leq 10$ .
$1 \leq \mathbf{N}, \mathbf{M} \leq 1000$ .
$1 \leq \mathbf{S_R}, \mathbf{T_R} \leq \mathbf{N}$ .
$1 \leq \mathbf{S_C}, \mathbf{T_C} \leq \mathbf{M}$ .
$0 \leq \mathbf{X_1},\mathbf{X_2},\mathbf{A},\mathbf{B},\mathbf{C} \leq \mathbf{P}$ .
$1 \leq \mathbf{P} \leq 100$ .

C++14(g++5.4) 解法, 执行用时: 1916ms, 内存消耗: 32216K, 提交时间: 2020-05-19 14:15:45

#include<iostream>
#include<algorithm>
using namespace std;
#define N 4000010
int T,n,m,sx,sy,ex,ey,tot,num;
int x1,x2,a,b,c,p;
int val[N],f[N];
long long ans=0;
struct node{
    int val,s,t;
    bool operator <(const node &a)const{
        return val>a.val;
    }
}t[N];


int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;int cnt=0;
    while(T--){
        ans=tot=num=0;
        cin>>n>>m>>sx>>sy>>ex>>ey;
        cin>>x1>>x2>>a>>b>>c>>p;
        for(int i=1;i<=n*m;i++) f[i]=i;
        val[1]=x1,val[2]=x2;
        for(int i=3;i<=n*m;i++)
            val[i]=(a*val[i-1]+b*val[i-2]+c)%p;
        for(int i=1;i<n*m;i++){
            if(i%m) t[++tot]={val[i]*val[i+1],i,i+1};
            if(i<=(n-1)*m) t[++tot]={val[i]*val[i+m],i,i+m};
        }
        sort(t+1,t+1+tot);
        for(int i=1;i<=tot;i++){
            node x=t[i];
            int t1=find(x.s),t2=find(x.t);
            if(t1!=t2) {
                f[t1] = t2, ans += x.val, num++;
                if(num==n*m-1) break;
            }
        }
        cout<<"Case #"<<++cnt<<": "<<ans<<endl;
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1736ms, 内存消耗: 43804K, 提交时间: 2020-10-07 14:40:05

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M=5e6+10;
int f[M];
struct node{
	int x,y;
	long long d;
	bool operator <(const node &a)const{
		return d>a.d;
	}
}w[M];
int fi(int x){
	return x==f[x]?x:f[x]=fi(f[x]);
}
long long ans,x1,x2,c,p,a[M];
int n,m,x,y,s,tt;
void mergy(int x,int y,ll d){
	int xx=fi(x),yy=fi(y);
	if(xx!=yy){
		f[xx]=yy;
		ans+=d;
	}
}
int main(){
	int t,T=1;
	scanf("%d",&t);
	while(t--){
		ans=0;
		scanf("%d%d%d%d%d%d",&n,&m,&x,&y,&s,&tt);
		scanf("%lld%lld%lld%lld%lld%lld",&a[1],&a[2],&x1,&x2,&c,&p);
		f[1]=1;
		f[2]=2;
		for(int i=3;i<=n*m;i++){
			a[i]=(x1*a[i-1]+x2*a[i-2]+c)%p;
			f[i]=i;
		}
		int len=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				int x=(i-1)*m+j;
				if(j!=m){
					w[len].x=x;
					w[len].y=x+1;
					w[len++].d=a[x]*a[x+1];
				}
				if(i!=n){
					w[len].x=x;
					w[len].y=x+m;
					w[len++].d=a[x]*a[x+m];
				}
			}
		}
		sort(w,w+len);
		for(int i=0;i<len;i++){
			mergy(w[i].x,w[i].y,w[i].d);
		}
		printf("Case #%d: %lld\n",T++,ans);
	}
	return 0;
}

详情