洛谷 P1967 货车运输

题目传送门

解题思路:

先求出整个图的最大生成树,然后做树上LCA.
AC代码:

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 
  5 using namespace std;
  6 
  7 int n,m,tot,head[10001],fa[10001],_tot,d[10001];
  8 int p[10001][21],q,fv[10001][21],ans = 0x7f7f7f7f;
  9 bool vis[10001];
 10 struct kkk{
 11     int vi,to,from;
 12 }e[100002];
 13 struct k2 {
 14     int next,v,to;
 15 }e1[100002];
 16 
 17 inline int find_father(int x) {
 18     if(fa[x] == x) return fa[x];
 19     return fa[x] = find_father(fa[x]);
 20 }
 21 
 22 inline void add(int x,int y,int z) {
 23     e[++tot].to = y;
 24     e[tot].vi = z;
 25     e[tot].from = x;
 26 }
 27 
 28 inline bool cmp(kkk a,kkk b) {
 29     return a.vi > b.vi;
 30 }
 31 
 32 inline void add2(int x,int y,int z) {
 33     e1[++_tot].to = y;
 34     e1[_tot].next = head[x];
 35     e1[_tot].v = z;
 36     head[x] = _tot;
 37 }
 38 
 39 inline void kruskal() {
 40     for(int i = 1;i <= n; i++) 
 41         fa[i] = i;
 42     sort(e+1,e+1+m+m,cmp);//因为是双向边,所以要加2*m,卡了好久,感谢Candy?大佬 
 43     for(int i = 1;i <= m + m; i++) {
 44         int t = e[i].to;
 45         int f = e[i].from;
 46         int tt = find_father(t);
 47         int ff = find_father(f);
 48         if(tt != ff) {
 49             add2(t,f,e[i].vi);
 50             add2(f,t,e[i].vi);
 51             fa[tt] = ff;
 52         }
 53     }
 54 }
 55 
 56 inline void dfs(int u) {
 57     vis[u] = 1;
 58     for(int i = 1;(1 << i) <= d[u]; i++){
 59         p[u][i] = p[p[u][i-1]][i-1];
 60         fv[u][i] = min(fv[u][i-1],fv[p[u][i-1]][i-1]);
 61     }
 62     for(int i = head[u];i != 0; i = e1[i].next) {
 63         int oo = e1[i].to;
 64         if(!vis[oo]) {
 65             d[oo] = d[u] + 1;
 66             fv[oo][0] = e1[i].v;//记录自己到父亲的边的值 
 67             p[oo][0] = u;//记录自己的父亲 
 68             dfs(oo);
 69         }
 70     }
 71 }
 72 
 73 inline int lca(int x,int y) {
 74     ans = 0x7f7f7f7f;
 75     if(find_father(x) != find_father(y)) return -1;
 76     if(d[x] > d[y])
 77         swap(x,y);
 78     for(int i = 20;i >= 0; i--)
 79         if(d[x] <= d[p[y][i]]) {
 80             ans = min(ans,fv[y][i]);
 81             y = p[y][i];
 82         }
 83     if(x == y) return ans;
 84     for(int i = 20;i >= 0; i--) {
 85         if(p[x][i] != p[y][i]) {
 86             ans = min(ans,min(fv[x][i],fv[y][i]));
 87             x = p[x][i];
 88             y = p[y][i];
 89         }
 90     }
 91     ans = min(ans,min(fv[x][0],fv[y][0]));
 92     return ans;
 93 }
 94 
 95 int main() {
 96     scanf("%d%d",&n,&m);
 97     for(int i = 1;i <= m; i++) {
 98         int x,y,z;
 99         scanf("%d%d%d",&x,&y,&z);
100         add(x,y,z);
101         add(y,x,z);
102     }
103     kruskal();
104     for(int i = 1;i <= n; i++)
105         if(!vis[i]) {
106             d[i] = 1; 
107             dfs(i);
108             p[i][0] = i;
109             fv[i][0] = 0x7f7f7f7f;
110         }
111     scanf("%d",&q);
112     for(int i = 1;i <= q; i++) {
113         int x,y;
114         scanf("%d%d",&x,&y);
115         printf("%d
",lca(x,y));
116     }
117     return 0;
118 }