P1967-开车旅行

川长思鸟来 2023-06-01 08:57 125阅读 0赞

1 #include <bits/stdc++.h>
      2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
      3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
      4 #define INF 0x3f3f3f3f
      5 #define pb push_back
      6 #define maxn 500003
      7 #define SWAP(x,y) x^=y,y^=x,x^=y
      8 typedef long long ll;
      9 using namespace std;
     10 
     11 inline ll read()
     12 {
     13     ll ans = 0;
     14     char ch = getchar(), last = ' ';
     15     while(!isdigit(ch)) last = ch, ch = getchar();
     16     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
     17     if(last == '-') ans = -ans;
     18     return ans;
     19 }
     20 inline void write(ll x)
     21 {
     22     if(x < 0) x = -x, putchar('-');
     23     if(x >= 10) write(x / 10);
     24     putchar(x % 10 + '0'); 
     25 }
     26 
     27 int N,M,S;
     28 vector<int> G[maxn*2];
     29 bool vis[maxn];
     30 int depth[maxn];
     31 int fa[maxn][25];
     32 int w[maxn][25];
     33 
     34 
     35 int par[maxn]; //父亲 
     36 int high[maxn]; //树的高度
     37 
     38 void init(int n)
     39 {
     40     _for(i,1,n+1)
     41     {
     42         par[i] = i;
     43         high[i] = 0;
     44     }
     45 } 
     46 
     47 int find(int x)
     48 {
     49     return par[x] == x ? x : par[x] = find(par[x]);
     50 }
     51 
     52 void unite(int x,int y)
     53 {
     54     x = find(x);y = find(y);
     55     if(x==y) return ;
     56     
     57     if(high[x]<high[y])
     58         par[x] = y;
     59     else
     60     {
     61         par[y] = x;
     62         if(high[x]==high[y])
     63             high[x] ++;
     64     }
     65 }
     66 
     67 bool same(int x,int y)
     68 {
     69     return find(x) == find(y); 
     70 }
     71 
     72 struct tedge
     73 {
     74     int u;
     75     int v;
     76     int cost;
     77 };
     78 int V,E;
     79 vector<tedge> es;
     80 vector<tedge> GG[maxn]; 
     81 bool cmp(const tedge& a,const tedge& b)
     82 {
     83     return a.cost > b.cost;
     84 } 
     85 void MST()
     86 {    
     87     sort(es.begin(),es.end(),cmp);
     88     init(V);
     89     _for(i,0,E)
     90     {
     91         tedge e = es[i];
     92         if(!same(e.u,e.v))
     93         {
     94             unite(e.u,e.v);
     95             GG[e.u].pb({e.u,e.v,e.cost});
     96             GG[e.v].pb({e.v,e.u,e.cost});
     97         } 
     98     }
     99 }
    100 
    101 void dfs(int u)
    102 {
    103     vis[u] = 1;
    104     _for(i,0,GG[u].size())
    105         if(!vis[GG[u][i].v])
    106         {
    107             depth[GG[u][i].v] = depth[u]+1;
    108             fa[GG[u][i].v][0] = u; 
    109             w[GG[u][i].v][0] = GG[u][i].cost;
    110             dfs(GG[u][i].v);
    111         }
    112 }
    113 void bz()
    114 {
    115     _for(j,1,21)
    116         _for(i,1,V+1)
    117         {
    118             fa[i][j] = fa[fa[i][j-1]][j-1];
    119             w[i][j] = min(w[i][j-1],w[fa[i][j-1]][j-1]);
    120         }
    121 //    cout << w[1][1] << endl;
    122 }
    123 int LCA(int u,int v)
    124 {
    125     
    126     //保证u深度较大 
    127     if(depth[u]<depth[v])
    128         swap(u,v);
    129     int ans = w[u][0];
    130     int dc = depth[u]-depth[v];
    131     
    132 _for(i,0,21)         if((1<<i)&dc)        {                        ans = min(ans,w[u][i]);    u=fa[u][i];    }
    133     
    134     if(u==v)    return ans;
    135     _rep(i,20,-1)
    136         if(fa[u][i]!=fa[v][i])
    137         {
    138             ans=min(ans,min(w[u][i],w[v][i]));
    139             u = fa[u][i],v = fa[v][i];
    140         }
    141     int val = w[u][0];
    142 //    if(fa[u][0]!=v)
    143         val = min(val,w[v][0]);
    144     return min(ans,val);
    145 }
    146 
    147 int main()
    148 {
    149 //    memset(fa,INF,sizeof(fa));
    150 //freopen("testdata.in","r+",stdin);
    151     memset(w,INF,sizeof(w));
    152     V = read();
    153     E = read();
    154     _for(i,1,E+1)
    155     {
    156         int a = read();
    157         int b = read();
    158         int c = read();
    159         es.pb({a,b,c});
    160     }
    161     MST();
    162     _for(i,1,V+1)
    163         if(i==par[i])
    164         {
    165             dfs(i);
    166         }
    167     bz();
    168 
    169     int Q = read();
    170     while(Q--)
    171     {
    172         int x = read();
    173         int y = read();
    174         if(find(x)!=find(y))
    175             printf("-1\n");
    176         else 
    177             printf("%d\n",LCA(x,y));
    178     }
    179     return 0;
    180 }

转载于:https://www.cnblogs.com/Asurudo/p/11590188.html