2 条题解

  • 0
    @ 2025-10-8 16:51:58
    #include <bits/stdc++.h>
    using namespace std;
    typedef pair<int, int> PII;
    const int N = 1e5 + 10;
    struct edge { int x, y, c; } E[N];
    vector<PII> G[N];
    int n, m, q, fa[N], f[N][21], g[N][21], dep[N], D;
    
    int findfa(int x) { return x == fa[x] ? x : fa[x] = findfa(fa[x]); }
    
    void dfs(int x, int ff) {
        dep[x] = dep[ff] + 1;
        f[x][0] = ff;
        for (int i = 1; i <= D; i++) f[x][i] = f[f[x][i-1]][i-1];
        for (int i = 1; i <= D; i++) g[x][i] = max(g[x][i-1], g[f[x][i-1]][i-1]);
        
        for (auto [y, w] : G[x]) if (y ^ ff)
            g[y][0] = w, dfs(y, x);
    }
    
    int query(int x, int y) {
        if (findfa(x) != findfa(y)) return -1;
        if (dep[x] < dep[y]) swap(x, y);
        int ans = 0;
        for (int i = D; i >= 0; --i) if (dep[f[x][i]] >= dep[y])
            ans = max(ans, g[x][i]), x = f[x][i];
        if (x == y) return ans;
        for (int i = D; i >= 0; --i) if (f[x][i] != f[y][i])
            ans = max({ans, g[x][i], g[y][i]}), x = f[x][i], y = f[y][i];
        return ans = max({ans, g[x][0], g[y][0]});
    }
    
    int main() {
        scanf("%d%d%d", &n, &m, &q);
        for (int i = 1; i <= m; ++i) scanf("%d%d%d", &E[i].x, &E[i].y, &E[i].c);
        sort(E + 1, E + m + 1, [&](edge a, edge b) { return a.c < b.c; });
        for (int i = 1; i <= n; ++i) fa[i] = i;
        for (int i = 1; i <= m; ++i) if (findfa(E[i].x) != findfa(E[i].y)) {
            G[E[i].x].push_back({E[i].y, E[i].c});
            G[E[i].y].push_back({E[i].x, E[i].c});
            fa[findfa(E[i].x)] = findfa(E[i].y);
        }
        memset(dep, 0, sizeof(dep)); D = log2(n);
        for (int i = 1; i <= n; ++i) if (!dep[i]) dfs(i, 0);
        while (q--) {
            int s, t; scanf("%d%d", &s, &t);
            printf("%d\n", query(s, t));
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:51:47
      #include<bits/stdc++.h>
      using namespace std;
      typedef pair<int,int> PII;
      const int N=1e5+10;
      struct edge{int x,y,c;}E[N];
      vector<PII>G[N];
      int n,m,q,fa[N],f[N][21],g[N][21],dep[N],D;;
      int findfa(int x) { return x==fa[x] ? x : fa[x]=findfa(fa[x]); }
      void dfs(int x, int ff)
      {
      	dep[x]=dep[ff]+1;
      	f[x][0]=ff;for(int i=1;i<=D;i++)f[x][i]=f[f[x][i-1]][i-1];
      	for(int i=1;i<=D;i++)g[x][i]=max(g[x][i-1],g[f[x][i-1]][i-1]);
      	
      	for(auto [y,w]:G[x])if(y^ff)
      		g[y][0]=w,
      		dfs(y,x);
      }
      int query(int x,int y)
      {
      	if(findfa(x)!=findfa(y)) return -1;
      	if (dep[x]<dep[y])swap(x,y);
      	int ans=0;
      	for(int i=D;i>=0;--i)if(dep[f[x][i]]>=dep[y])ans=max(ans,g[x][i]),x=f[x][i];
      	if(x==y) return ans;
      	for(int i=D;i>=0;--i)if(f[x][i]!= f[y][i])
      		ans=max({ans,g[x][i],g[y][i]}),
      		x=f[x][i],y=f[y][i];
      	return ans=max({ans,g[x][0],g[y][0]});
      }
      int main()
      {
      	scanf("%d%d%d",&n,&m,&q);
      	for(int i=1;i<=m;++i) scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].c);
      	sort(E+1,E+m+1,[&](edge a,edge b){return a.c<b.c;});
      	for(int i=1;i<=n;++i)fa[i]=i;
      	for(int i=1;i<=m;++i)if(findfa(E[i].x)!=findfa(E[i].y))
      	{
      		G[E[i].x].push_back({E[i].y,E[i].c});
      		G[E[i].y].push_back({E[i].x,E[i].c}); 
      		fa[findfa(E[i].x)]=findfa(E[i].y);
      	}
      	memset(dep,0,sizeof(dep));D=log2(n);
      	for(int i=1;i<=n;++i)if(!dep[i])dfs(i,0);
      	while(q--)
      	{
      		int s,t;scanf("%d%d",&s,&t);
      		printf("%d\n",query(s,t));
      	}
      	return 0;
      }
      • 1

      *【最近公共祖先+Kruskal】最小瓶颈路[LOJ136]

      信息

      ID
      721
      时间
      1000ms
      内存
      128MiB
      难度
      9
      标签
      (无)
      递交数
      9
      已通过
      6
      上传者