本文共 4938 字，大约阅读时间需要 16 分钟。

问题描述

【题目描述】

7 10 41 3 102 6 94 1 53 7 43 6 91 5 82 7 43 2 101 7 67 6 91 7 1 01 7 3 12 5 1 03 7 2 1

【样例输出】

9688

题目解析

最小生成树简单算法

对于每一次问询，关注若干点后，我们需要按照最小生成树的方法生成n-1条边，此时关注点全部连通，然后求出其中的最大边就是答案。

倍增法优化最小生成树

新思路

1. 首先生成最小生成树$MST$；
2. 对每一次问询都要将关注点放入$MST$；
3. 维护$maxcost$；
   在维护$maxcost$用到倍增法求最近公共祖先lca，倍增法就是要用额外的数据来存放每一个点。$ff[i][j]$表示点i向上移动$2^i$次到达节点的标号。

倍增法LCA

1. 对$ff[][]$数组进行预处理，用到了$dfs$算法；
2. 求$lca$，将$a$和$b$调到同一个高度；
3. 在2的过程中维护$max$、$sum$、$avg$、$min$。

C++代码

最小生成树简单算法

#include
   
    using namespace std;int N,M,Q;const int MaxM = 2*10^5;const int MaxN = 50001;struct Edge //边的抽象{
       int from,to,cost; //起点终点代价    Edge(int from,int to,int cost)    {
           this->from = from;        this->to = to;        this->cost = cost;    }};bool cmp(Edge *e1,Edge *e2){
       return e1->cost
    
     cost;}Edge *edges[MaxM];//并查集struct UFNode{
       UFNode *parent;    UFNode():parent(NULL){
   }};UFNode *find(UFNode *p){
       if(p->parent==NULL) return p;    set
     
       path;    while(p->parent!=NULL)    {
           path.insert(p);        p = p->parent;    }    set
      
       ::iterator iter = path.begin();    while(iter!=path.end())    {
           (*iter)->parent=p;        iter++; //指针后移    }    return p;}void merge(UFNode *p1,UFNode *p2) //并查集合并{
       find(p2)->parent = find(p1);}UFNode ufnodes[MaxN]; //并查集的节点，一开始各自独立void easy(int l,int r,int mod,int c){
       for(int j=0;j<=N;j++) ufnodes[j].parent = NULL; //重新初始化NULL    //逐步加入边到最小生成树中    for(int i=0;i
       
        from;        int to = pEdge->to;        int cost = pEdge->cost;        if(find(&ufnodes[from])==find(&ufnodes[to])) continue; //如果这两个点已经在一棵树上就不采纳        else merge(&ufnodes[from],&ufnodes[to]); //并查集合并        UFNode * parent = NULL;        bool isOk = true;        for(int i=l;i<=r;i++)        {
               if(i%mod==c) //i值关注点的编号            {
                   if(parent==NULL) parent = find(&ufnodes[i]); //第一个关注点的老大                else if(parent!=find(&ufnodes[i])) //没有联通                {
                       isOk = false;                    break;                }            }        }        if(isOk) //关注点都联通了        {
               printf("%d\n",cost);            break;        }    }}int main(){
       scanf("%d %d %d",&N,&M,&Q);    for(int i=0;i
       
      
     
    
   

倍增法优化最小生成树代码

#include
   
    using namespace std;int N,M,Q;const int MaxM = 2*10^5;const int MaxN = 50001;int ff[MaxN][17]; //ff[i][j]表示标号为i的节点往根节点的方向移动2^i次达到的节点编号int mm[MaxN][17]; //mm[i][j]指的是标号为i的节点往根节点的方向移动2^i次过程中的最大权int depth[MaxN]; //记录每个点在mst中的深度int vis[MaxN]; //记录耨个是否被访问过struct Edge //边的抽象{
       int from,to,cost; //起点终点代价    Edge(int from,int to,int cost)    {
           this->from = from;        this->to = to;        this->cost = cost;    }};bool cmp(Edge *e1,Edge *e2){
       return e1->cost
    
     cost;}Edge *edges[MaxM];//并查集struct UFNode{
       UFNode *parent;    UFNode():parent(NULL){
   }};UFNode *find(UFNode *p){
       if(p->parent==NULL) return p;    set
     
       path;    while(p->parent!=NULL)    {
           path.insert(p);        p = p->parent;    }    set
      
       ::iterator iter = path.begin();    while(iter!=path.end())    {
           (*iter)->parent=p;        iter++; //指针后移    }    return p;}void merge(UFNode *p1,UFNode *p2) //并查集合并{
       find(p2)->parent = find(p1);}UFNode ufnodes[MaxN]; //并查集的节点，一开始各自独立int maxUsingLca(int a,int b) //倍增法求lca顺便求max权重{
       int ans = -1;    if(depth[a]
       
        =0;j--)    {
           if(ff[a][j]==ff[b][j]) continue;        else        {
               ans = max(ans,mm[a][j]);            ans = max(ans,mm[b][j]);            a = ff[a][j];            b = ff[b][j];            break;        }    }    ans = max(ans,mm[a][0]);    ans = max(ans,mm[b][0]); //再往上走一步就得到了lca    return ans;}void mid(int l,int r,int mod,int c){
       int ans = -1;    int left = l-l%mod+c;    if(left
        
          mst[MaxN];void buildMST(){ int cnt = 0; //已加入边的数量 //逐步加入边到最小生成树中 for(int i=0;i
         
          from; int to = pEdge->to; int cost = pEdge->cost; if(find(&ufnodes[from])==find(&ufnodes[to])) continue; //如果这两个点已经在一棵树上就不采纳 else { merge(&ufnodes[from],&ufnodes[to]); //并查集合并 cnt++; mst[from].push_back(pEdge); Edge *other = new Edge(to,from,cost); mst[to].push_back(other); if(cnt==N-1) //构建完成 { break; } } }}void dfs(int start,int parent,int d) //start表示开始点编号，parent表示父结点编号，d表示这个点的深度{ depth[start] = d+1; vis[start] = 1; //向上走 for(int i=1;i<17;i++) { ff[start][i] = ff[ff[start][i-1]][i-1]; mm[start][i] = max(mm[start][i-1],mm[ff[start][i-1]][i-1]); } //向下递归找到所有儿子 for(int i=0;i
          
           to]) continue; ff[child->to][0] = start; mm[child->to][0] = child->cost; dfs(child->to,start,d+1); }}void preLca(){ ff[1][0] = 1; //定义1号节点为树的根节点 mm[1][0] = 0; //定义1号节点为根节点 dfs(1,1,0);}int main(){ scanf("%d %d %d",&N,&M,&Q); for(int i=0;i
          
         
        
       
      
     
    
   

转载地址：http://ozqu.baihongyu.com/