2 条题解
-
0
#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
#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
信息
- ID
- 721
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 9
- 已通过
- 6
- 上传者