2019上海ICPC E.Cave Escape

E.Cave Escape

比赛时候过的人很少，感觉应该是都被卡题了没有读这个题，或者榜歪了？

题意：就是说给了一个n * m的矩阵，对于位置(i,j)的能量为x_(i-1)m+j
起点在(ex,ey) 终点在(sx,sy) 当你从一个位置*第一次**走到另一个位置的时候，获得的值就是这两个格子能量相乘，每个点可以多次到达，不限制走的步数，就是说你可以随便走，但获得的值只能是第一次走到才有效计算。

思路：
要获得的值最大，又可以随便走，那最优策略就是把整个矩阵都走一遍··，然后出去就好了。
整个矩阵都走一遍，意味着整个矩阵联通。也就是把矩阵每个点都抽离出来当作图的一个点，意味着要求联通后的最大值。
那不就是最小生成树吗
首先把x_(i,j)处理出来，计算每个点与相邻之间四个点的权值，就是两点之间的能量相乘。然后跑一次克鲁斯卡尔求最大值即可。
对于边的处理，我们只需要处理当前点与他上边和左边的点即可，至于他与右边和下边的点，在遍历的时候也会算进去的，这样做可以保证不重不漏。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1405;
int p;
int x[maxn*maxn];
int v[maxn][maxn];
struct node
{
    int x,y;
    int v;
}a[maxn*maxn];
int f[maxn*maxn];
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
int main(){
    int t;scanf("%d",&t);
    int cas=0;
    while(t--){
        int n,m,ff,g,h,l;scanf("%d%d%d%d%d%d",&n,&m,&ff,&g,&h,&l);
        int A,B,C;
        scanf("%d%d%d%d%d%d",&x[1],&x[2],&A,&B,&C,&p);
        for(int i=3;i<=n*m;i++) x[i]=(A*x[i-1]+B*x[i-2]+C)%p;
         int cnt=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                f[(i-1)*m+j]=(i-1)*m+j;
                v[i][j]=x[(i-1)*m+j];
                 if(i-1>=1){
                    a[cnt].x=((i-1)*m+j);
                    a[cnt].y=((i-2)*m+j);
                    a[cnt].v=v[i-1][j]*v[i][j];
                    cnt++;
                }
                if(j-1>=1){
                    a[cnt].x=((i-1)*m+j);
                    a[cnt].y=((i-1)*m+j-1);
                    a[cnt].v=v[i][j-1]*v[i][j];
                    cnt++;
                }
            }
        }
        sort(a,a+cnt,[](node a,node b){

            return a.v>b.v;
        });
        long long  sum=0;
        int num=0;
        for(int i=0;i<cnt;i++){
            int fx=find(a[i].x),fy=find(a[i].y);
            if(fx!=fy){
                sum+=a[i].v;
                f[fx]=fy;
                num++;
                if(num==n*m-1) break;
            }
        }
        printf("Case #%d: %lld\n",++cas,sum);

    }

    return 0;
}