2019 icpc 上海站 H Cave Escape 最大生成树

题目链接：https://ac.nowcoder.com/acm/contest/6234/H
题目大意：你可以按题目规则规则一个矩阵

然后问你从(Sr, Sc)到(Tr, Tc)的最大分数，如果(x, y)没有访问过，那么你从(i, j)访问到(x, y)得到发分数为V(i, j)*V(x, y)。

思路：因为vij>0那么我们一定是把所有的点访问完的代价最大。然后每个点向周围四个方向连边就是求一个最大生成树。
优化：我们从题目可以知道边权<10000，边可以桶排。得到n-1条边就break。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

LL x[1000*1005];
struct node{
    LL u, v, w;
};
int f[1000*1005*2];
int fd(int x){
    if(f[x]==-1) return x;
    return f[x]=fd(f[x]);
}
vector<node> v[10005];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main(){

    int T, cas=1; scanf("%d", &T);
    while(T--){
        for(int i=0; i<=10000; i++) {
            v[i].clear();//必须先加这一句，否则直接用v.shrink_to_fit(),无法释放内存
            v[i].shrink_to_fit();
        }
        LL N, M, Sr, Sc, Tr, Tc;
        N=read(), M=read(), Sr=read(), Sc=read(), Tr=read(), Tc=read();
        LL x1, x2, A, B, C, P;
        x[1]=read(), x[2]=read(), A=read(), B=read(), C=read(), P=read();
        f[1]=f[2]=-1;
        for(int i=3; i<=N*M; ++i){
            x[i]=(A*x[i-1]+B*x[i-2]+C)%P;
            f[i]=-1;
        }
        for(int i=1; i<=N; ++i){
            for(int j=1; j<=M; ++j){
                if(i+1<=N){
                    int s = (i-1)*M + j;
                    int t = i*M + j;
                    v[x[s]*x[t]].push_back({s, t});
                }
                if(j+1<=M){
                    int s = (i-1)*M + j;
                    int t = (i-1)*M+j+1;
                    v[x[s]*x[t]].push_back({s, t});
                }
            }
        }
        LL ans=0, now=N*M-1;
        for(int i=10000; i>=0&&now>0; i--){
            for(auto To: v[i]){
                int x=fd(To.u), y=fd(To.v);
                if(x!=y){
                    ans+=i;
                    f[x]=y;
                    --now;
                }
            }
        }
        printf("Case #%d: %lld\n", cas++, ans);
    }

    return 0;
}