Mountaineers Gym

题目链接:

Mountaineers

 Gym - 102021M 

题目大意:给你一个n*m的矩阵,a[i][j]代表当前方块的高度,然后每次询问给你一个起点和终点,然后问你在这个图上你选择一条路径,使得这条路径上的最大值尽可能的小,然后输出最大值。

具体思路:用最小生成树进行建图,首先对每个点的权值按照从小到大进行排序。每次是把上一次连通块的根作为当前的节点的儿子。正好保证了整个图是联通的,并且询问起点和中点的时候,在树上找lca就可以了。

AC代码:

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 # define ll long long
  4 # define inf 0x3f3f3f3f
  5 const int maxn = 2e6+100;
  6 int father[maxn];
  7 int vis[500+100][500+100];
  8 int sto[maxn];
  9 struct node
 10 {
 11     int x,y,id,val;
 12     node() {}
 13     node(int xx,int yy,int zz,int kk)
 14     {
 15         x=xx,y=yy,id=zz,val=kk;
 16     }
 17     bool friend operator < (node t1,node t2)
 18     {
 19         return t1.val<t2.val;
 20     }
 21 } q[maxn];
 22 vector<int>Edge[maxn];
 23 int Find(int t)
 24 {
 25     return t==father[t]?t:father[t]=Find(father[t]);
 26 }
 27 int depth[maxn];
 28 int fa[maxn][22];
 29 void dfs(int u,int root)
 30 {
 31     depth[u]=depth[root]+1;
 32     fa[u][0]=root;
 33     for(int i=1; (1<<i)<=depth[u]; i++)
 34     {
 35         fa[u][i]=fa[fa[u][i-1]][i-1];
 36     }
 37     for(int i=0; i<Edge[u].size(); i++)
 38     {
 39         int to=Edge[u][i];
 40         if(to==root)
 41             continue;
 42         dfs(to,u);
 43     }
 44 }
 45 int lca(int t1,int t2)
 46 {
 47     if(depth[t1]>depth[t2])
 48         swap(t1,t2);
 49     for(int i=20; i>=0; i--)
 50     {
 51         if(depth[t1]<=depth[t2]-(1<<i))
 52         {
 53             t2=fa[t2][i];
 54         }
 55     }
 56     if(t1==t2)
 57         return t1;
 58     for(int i=20; i>=0; i--)
 59     {
 60         if(fa[t1][i]!=fa[t2][i])
 61         {
 62             t1=fa[t1][i];
 63             t2=fa[t2][i];
 64         }
 65     }
 66     return fa[t1][0];
 67 }
 68 int main()
 69 {
 70     int n,m,qq,tmp;
 71     int cnt=0;
 72     scanf("%d %d %d",&n,&m,&qq);
 73     for(int i=1; i<=n; i++)
 74     {
 75         for(int j=1; j<=m; j++)
 76         {
 77             scanf("%d",&tmp);
 78             sto[++cnt]=tmp;
 79             father[cnt]=cnt;
 80             q[cnt]=node(i,j,cnt,tmp);
 81         }
 82     }
 83     sort(q+1,q+cnt+1);
 84     int t1,t2;
 85     for(int i=1; i<=cnt; i++)
 86     {
 87         if(q[i].x!=1&&vis[q[i].x-1][q[i].y]&&Find(q[i].id-m)!=Find(q[i].id)){
 88         int t1=Find(q[i].id-m);
 89         int t2=Find(q[i].id);
 90         Edge[q[i].id].push_back(t1);
 91         father[t1]=q[i].id;
 92         }
 93         if(q[i].x!=n&&vis[q[i].x+1][q[i].y]&&Find(q[i].id+m)!=Find(q[i].id)){
 94         int t1=Find(q[i].id+m);
 95         int t2=Find(q[i].id);
 96         Edge[q[i].id].push_back(t1);
 97         father[t1]=q[i].id;
 98         }
 99         if(q[i].y!=1&&vis[q[i].x][q[i].y-1]&&Find(q[i].id-1)!=Find(q[i].id)){
100         int t1=Find(q[i].id-1);
101         int t2=Find(q[i].id);
102         Edge[q[i].id].push_back(t1);
103         father[t1]=q[i].id;
104         }
105         if(q[i].y!=m&&vis[q[i].x][q[i].y+1]&&Find(q[i].id+1)!=Find(q[i].id)){
106         int t1=Find(q[i].id+1);
107         int t2=Find(q[i].id);   
108         Edge[q[i].id].push_back(t1);
109         father[t1]=q[i].id;
110         }
111         vis[q[i].x][q[i].y]=1;
112     }
113     dfs(Find(1),0);
114     while(qq--)
115     {
116         int x1,y1,x2,y2;
117         scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
118         printf("%d
",sto[lca((x1-1)*m+y1,(x2-1)*m+y2)]);
119     }
120     return 0;
121 }
原文地址:https://www.cnblogs.com/letlifestop/p/10779142.html