( ext{Description})
( ext{Solution})
我们先构造出一棵最小生成树然后分类讨论。
- 非树边:这个比较套路,只要使 (e[i].w) 等于 (u,v) 在树上路径中最大权值的边就有可能选中。
- 树边:从非树边的思路拓展。其实,只要 (u,v) 在树上路径中的边包含这条树边,这条非树边就造成影响,我们选取这些非树边中权值最小的,超过这个肯定就会被这条非树边代替。
非树边 (mathcal{O(mlog n)}),然而树边不加优化会 ( ext{T})。
我们从小到大枚举非树边,那么每条边 (u,v) 树上路径中的边的 (ans) 就是这条非树边,之后就不用管那些边了,我们把这些边压缩至冰茶姬即可。
( ext{Code})
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+5,M=1e6+5,inf=1e9;
int n,m,fa[N],cnt,nxt[N<<1],to[N<<1],val[N<<1],head[N],dep[N],f[N][22],mx[N][22],ans[M],p,ip[N<<1],edge[N];
bool ok[M];
struct Edge {int u,v,w,i;} e[M],E[M];
int read() {
int x=0,f=1; char s;
while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
void addEdge(int u,int v,int w,int ID) {
nxt[++cnt]=head[u],to[cnt]=v,head[u]=cnt,val[cnt]=w,ip[cnt]=ID;
}
void init() {for(int i=1;i<=n;++i) fa[i]=i;}
int Find(int x) {return x==fa[x]?x:fa[x]=Find(fa[x]);}
void dfs(int u,int ba) {
dep[u]=dep[ba]+1; f[u][0]=ba;
for(int i=1;i<=20;++i) f[u][i]=f[f[u][i-1]][i-1],mx[u][i]=max(mx[u][i-1],mx[f[u][i-1]][i-1]);
for(int i=head[u];i;i=nxt[i]) {
int v=to[i];
if(v==ba) continue;
mx[v][0]=val[i]; edge[v]=ip[i];
dfs(v,u);
}
}
int LCA(int u,int v) {
if(dep[v]>dep[u]) swap(u,v);
int r=0;
for(int i=20;i>=0;--i)
if(dep[f[u][i]]>=dep[v]) {
r=max(r,mx[u][i]);
u=f[u][i];
}
if(u==v) return r;
for(int i=20;i>=0;--i)
if(f[u][i]^f[v][i]) {
r=max(r,max(mx[u][i],mx[v][i]));
u=f[u][i]; v=f[v][i];
}
return max(r,max(mx[u][0],mx[v][0]));
}
bool cmp(Edge a,Edge b) {return a.w<b.w;}
void Kruskal() {
sort(e+1,e+m+1,cmp); init();
for(int i=1;i<=m;++i) {
int u=e[i].u,v=e[i].v;
if(Find(u)^Find(v)) {
fa[Find(u)]=Find(v);
ok[e[i].i]=1;
addEdge(u,v,e[i].w,e[i].i),addEdge(v,u,e[i].w,e[i].i);
}
}
}
int Lca(int u,int v) {
if(dep[v]>dep[u]) swap(u,v);
for(int i=20;i>=0;--i)
if(dep[f[u][i]]>=dep[v]) u=f[u][i];
if(u==v) return u;
for(int i=20;i>=0;--i)
if(f[u][i]^f[v][i])
u=f[u][i],v=f[v][i];
return f[u][0];
}
void jump(int u,int v,int w) {
if(dep[u]<dep[v]) swap(u,v);
int lca=Lca(u,v);
if(Find(u)^u) u=Find(u);
if(Find(v)^v) v=Find(v);
while(dep[u]>dep[lca]) {
ans[edge[u]]=w;
fa[u]=Find(f[u][0]);
u=Find(f[u][0]);
}
while(dep[v]>dep[lca]) {
ans[edge[v]]=w;
fa[v]=Find(f[v][0]);
v=Find(f[v][0]);
}
}
int main() {
int u,v,w;
memset(ans,-1,sizeof ans);
n=read(),m=read();
for(int i=1;i<=m;++i) {
u=read(),v=read(),w=read();
e[i]=(Edge) {u,v,w,i};
}
Kruskal(); init(); dfs(1,0);
for(int i=1;i<=m;++i) {
if(ok[e[i].i]) continue;
ans[e[i].i]=LCA(e[i].u,e[i].v);
E[++p]=e[i];
}
for(int i=1;i<=p;++i) jump(E[i].u,E[i].v,E[i].w);
for(int i=1;i<=m;++i) printf("%d
",ans[i]==-1?inf:ans[i]);
return 0;
}