LuoguP1967 货车运输 LCA

lca的倍增策略不仅可以维护最近公共祖先，还可以维护其他具有区间可维护性的信息，例如本题中维护的最小限重。

本题调了好久，最后发现原因是数组用混了。以后一定要记准各个数组含义，千万不要混啊。。。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<vector>
  6 
  7 using namespace std;
  8 
  9 const int Maxn = 1e5+10,Maxm = 5e5+10;
 10 
 11 struct Edge{
 12     int fr,to,wi;
 13     bool operator <(const Edge& x)const{
 14         return wi > x.wi;
 15     }
 16 }edges[Maxm],e;
 17 
 18 struct node{int to,wi;};
 19 
 20 int n,m,x,y,z,cnte,q;
 21 vector<node> g[Maxn];
 22 
 23 int read(){
 24     int ans = 0;char last = ' ',ch = getchar();
 25     while(ch < '0'||ch > '9')last = ch,ch = getchar();
 26     while('0' <= ch&&ch <= '9')ans = ans*10+ch-'0',ch = getchar();
 27     if(last == '-')return -ans;return ans;
 28 }
 29 
 30 int fa[Maxn];
 31 int find(int x){
 32     if(fa[x] == x)return x;
 33     return fa[x] = find(fa[x]);
 34 }
 35 
 36 void kruscal(){
 37     sort(edges+1,edges+m+1);
 38     for(int i = 1;i <= n;i++)fa[i] = i;
 39     for(int i = 1;i <= m;i++){
 40         e = edges[i];
 41         if(find(e.fr) != find(e.to)){
 42             fa[fa[e.fr]] = fa[e.to];
 43             g[e.fr].push_back((node){e.to,e.wi});
 44             g[e.to].push_back((node){e.fr,e.wi});
 45         }
 46     }
 47 }
 48 
 49 int jump[Maxn][20],wide[Maxn][20];
 50 int dep[Maxn];
 51 
 52 void workdep(int rt,int fa){
 53     dep[rt] = dep[fa]+1;
 54     for(int i = 0;i < g[rt].size();i++){
 55         int to = g[rt][i].to,wi = g[rt][i].wi;
 56         if(to == fa)continue;
 57         jump[to][0] = rt;
 58         wide[to][0] = wi;
 59         workdep(to,rt);
 60     }
 61 }
 62 
 63 void initall(){
 64     for(int i = 1;i <= 18;i++)
 65         for(int j = 1;j <= n;j++){
 66             jump[j][i] = jump[jump[j][i-1]][i-1];
 67             wide[j][i] = min(wide[j][i-1],wide[jump[j][i-1]][i-1]);
 68         }    
 69 }
 70 
 71 int ask(int x,int y){
 72     int ans = 1<<30;
 73     if(find(x) != find(y))return -1;
 74     int dx = dep[x],dy = dep[y];
 75     if(dx < dy)swap(x,y),swap(dx,dy);//printf("start::%d,%d:%d
",x,y,ans);
 76     for(int i = 18;i >= 0;i--)if(dep[jump[x][i]] > dy){
 77         ans = min(ans,wide[x][i]);
 78         x = jump[x][i];//printf("->%d,%d:%d
",x,y,ans);
 79     }
 80     if(dx != dy){
 81         ans = min(ans,wide[x][0]);//printf("->%d,%d:%d
",x,y,ans);
 82         if((x=jump[x][0]) == y)return ans;//printf("->%d,%d:%d
",x,y,ans);
 83     }
 84     for(int i = 18;i >= 0;i--)if(jump[x][i] != jump[y][i]){
 85         ans = min(ans,min(wide[x][i],wide[y][i]));
 86         x = jump[x][i],y = jump[y][i];//printf("->%d,%d:%d
",x,y,ans);
 87     }
 88 //    cout << "ans::";
 89     return min(ans,min(wide[x][0],wide[y][0]));
 90 }
 91 
 92 int main(){
 93     n = read(),m = read();
 94     for(int i = 1;i <= m;i++)edges[i] = (Edge){read(),read(),read()};
 95     q = read();
 96     kruscal();
 97     memset(wide,0x3f,sizeof(wide));
 98     for(int i = 1;i <= n;i++)if(!dep[i])workdep(i,0);
 99 //    cout << "dep[]: ";for(int i = 1;i <= n;i++)cout << dep[i] << ' ';cout << endl;
100     initall();
101     
102 /*    for(int i = 0;i <= 18;i++){
103         for(int j = 1;j <= n;j++)printf("%d ",jump[j][i]);
104         putchar('
');
105     }
106     putchar('
');
107     for(int i = 0;i <= 18;i++){
108         for(int j = 1;j <= n;j++)printf("%d ",wide[j][i]);
109         putchar('
');
110     }
111     putchar('
');*/
112     
113     while(q--)printf("%d
",ask(read(),read()));
114 return 0;
115 }

调试代码

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<vector>
  6 
  7 using namespace std;
  8 
  9 const int Maxn = 1e5+10,Maxm = 5e5+10;
 10 
 11 struct Edge{
 12     int fr,to,wi;
 13     bool operator <(const Edge& x)const{
 14         return wi > x.wi;
 15     }
 16 }edges[Maxm],e;
 17 
 18 struct node{int to,wi;};
 19 
 20 int n,m,x,y,z,cnte,q;
 21 vector<node> g[Maxn];
 22 
 23 int read(){
 24     int ans = 0;char last = ' ',ch = getchar();
 25     while(ch < '0'||ch > '9')last = ch,ch = getchar();
 26     while('0' <= ch&&ch <= '9')ans = ans*10+ch-'0',ch = getchar();
 27     if(last == '-')return -ans;return ans;
 28 }
 29 
 30 int fa[Maxn];
 31 int find(int x){
 32     if(fa[x] == x)return x;
 33     return fa[x] = find(fa[x]);
 34 }
 35 
 36 void kruscal(){
 37     sort(edges+1,edges+m+1);
 38     for(int i = 1;i <= n;i++)fa[i] = i;
 39     for(int i = 1;i <= m;i++){
 40         e = edges[i];
 41         if(find(e.fr) != find(e.to)){
 42             fa[fa[e.fr]] = fa[e.to];
 43             g[e.fr].push_back((node){e.to,e.wi});
 44             g[e.to].push_back((node){e.fr,e.wi});
 45         }
 46     }
 47 }
 48 
 49 int jump[Maxn][20],wide[Maxn][20];
 50 int dep[Maxn];
 51 
 52 void workdep(int rt,int fa){
 53     dep[rt] = dep[fa]+1;
 54     for(int i = 0;i < g[rt].size();i++){
 55         int to = g[rt][i].to,wi = g[rt][i].wi;
 56         if(to == fa)continue;
 57         jump[to][0] = rt;
 58         wide[to][0] = wi;
 59         workdep(to,rt);
 60     }
 61 }
 62 
 63 void initall(){
 64     for(int i = 1;i <= 18;i++)
 65         for(int j = 1;j <= n;j++){
 66             jump[j][i] = jump[jump[j][i-1]][i-1];
 67             wide[j][i] = min(wide[j][i-1],wide[jump[j][i-1]][i-1]);
 68         }    
 69 }
 70 
 71 int ask(int x,int y){
 72     int ans = 1<<30;
 73     if(find(x) != find(y))return -1;
 74     int dx = dep[x],dy = dep[y];
 75     if(dx < dy)swap(x,y),swap(dx,dy);
 76     for(int i = 18;i >= 0;i--)if(dep[jump[x][i]] > dy){
 77         ans = min(ans,wide[x][i]);
 78         x = jump[x][i];
 79     }
 80     if(dx != dy){
 81         ans = min(ans,wide[x][0]);
 82         if((x=jump[x][0]) == y)return ans;
 83     }
 84     for(int i = 18;i >= 0;i--)if(jump[x][i] != jump[y][i]){
 85         ans = min(ans,min(wide[x][i],wide[y][i]));
 86         x = jump[x][i],y = jump[y][i];
 87     }
 88     return min(ans,min(wide[x][0],wide[y][0]));
 89 }
 90 
 91 int main(){
 92     n = read(),m = read();
 93     for(int i = 1;i <= m;i++)edges[i] = (Edge){read(),read(),read()};
 94     q = read();
 95     kruscal();
 96     memset(wide,0x3f,sizeof(wide));
 97     for(int i = 1;i <= n;i++)if(!dep[i])workdep(i,0);
 98     initall();
 99     while(q--)printf("%d
",ask(read(),read()));
100 return 0;
101 }

Final