Mountaineers Gym - 102021M (LCA+MST)

题目链接：

Mountaineers

Gym - 102021M

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

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

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 # define ll long long

 # define inf 0x3f3f3f3f

 const int maxn = 2e6+;

 int father[maxn];

 int vis[+][+];

 int sto[maxn];

 struct node

 {

     int x,y,id,val;

     node() {}

     node(int xx,int yy,int zz,int kk)

     {

         x=xx,y=yy,id=zz,val=kk;

     }

     bool friend operator < (node t1,node t2)

     {

         return t1.val<t2.val;

     }

 } q[maxn];

 vector<int>Edge[maxn];

 int Find(int t)

 {

     return t==father[t]?t:father[t]=Find(father[t]);

 }

 int depth[maxn];

 int fa[maxn][];

 void dfs(int u,int root)

 {

     depth[u]=depth[root]+;

     fa[u][]=root;

     for(int i=; (<<i)<=depth[u]; i++)

     {

         fa[u][i]=fa[fa[u][i-]][i-];

     }

     for(int i=; i<Edge[u].size(); i++)

     {

         int to=Edge[u][i];

         if(to==root)

             continue;

         dfs(to,u);

     }

 }

 int lca(int t1,int t2)

 {

     if(depth[t1]>depth[t2])

         swap(t1,t2);

     for(int i=; i>=; i--)

     {

         if(depth[t1]<=depth[t2]-(<<i))

         {

             t2=fa[t2][i];

         }

     }

     if(t1==t2)

         return t1;

     for(int i=; i>=; i--)

     {

         if(fa[t1][i]!=fa[t2][i])

         {

             t1=fa[t1][i];

             t2=fa[t2][i];

         }

     }

     return fa[t1][];

 }

 int main()

 {

     int n,m,qq,tmp;

     int cnt=;

     scanf("%d %d %d",&n,&m,&qq);

     for(int i=; i<=n; i++)

     {

         for(int j=; j<=m; j++)

         {

             scanf("%d",&tmp);

             sto[++cnt]=tmp;

             father[cnt]=cnt;

             q[cnt]=node(i,j,cnt,tmp);

         }

     }

     sort(q+,q+cnt+);

     int t1,t2;

     for(int i=; i<=cnt; i++)

     {

         if(q[i].x!=&&vis[q[i].x-][q[i].y]&&Find(q[i].id-m)!=Find(q[i].id)){

         int t1=Find(q[i].id-m);

         int t2=Find(q[i].id);

         Edge[q[i].id].push_back(t1);

         father[t1]=q[i].id;

         }

         if(q[i].x!=n&&vis[q[i].x+][q[i].y]&&Find(q[i].id+m)!=Find(q[i].id)){

         int t1=Find(q[i].id+m);

         int t2=Find(q[i].id);

         Edge[q[i].id].push_back(t1);

         father[t1]=q[i].id;

         }

         if(q[i].y!=&&vis[q[i].x][q[i].y-]&&Find(q[i].id-)!=Find(q[i].id)){

         int t1=Find(q[i].id-);

         int t2=Find(q[i].id);

         Edge[q[i].id].push_back(t1);

         father[t1]=q[i].id;

         }

         if(q[i].y!=m&&vis[q[i].x][q[i].y+]&&Find(q[i].id+)!=Find(q[i].id)){

         int t1=Find(q[i].id+);

         int t2=Find(q[i].id);

         Edge[q[i].id].push_back(t1);

         father[t1]=q[i].id;

         }

         vis[q[i].x][q[i].y]=;

     }

     dfs(Find(),);

     while(qq--)

     {

         int x1,y1,x2,y2;

         scanf("%d %d %d %d",&x1,&y1,&x2,&y2);

         printf("%d\n",sto[lca((x1-)*m+y1,(x2-)*m+y2)]);

     }

     return ;

 }

巴特西

Mountaineers Gym - 102021M (LCA+MST)

Mountaineers

最新文章

热门文章