题解 P4180 【【模板】严格次小生成树[BJWC2010]】
——我好难,QAQ
这道题卡了我一下午！
就是这样的，然而很有意思的是中间发生了十分多的事，比如：当我发现了我的一个错误的时候，我很开心的以为我可以A了，结果——换了一个点WA（太棒了！），然后我果断弃了此题。直到第二天，我又重新打了一遍，然后，我就想到了一个问题，成功切了这道毒瘤题……
总而言之，我太菜了！
想必这道题的思路是很明确的——LCA+最小生成树，因为我不会LCT。
我的问题在于，原先我的思路是，次小生成树，这并不严格……所以：
80分：
int lca(int x,int y,int z){
if (find(x)!=find(y)) return -1;
if (dep[x]<dep[y]) swap(x,y);
int d=dep[x]-dep[y],ans=0;
for (int i=0;(1<<i)<=d;i++)
if ((1<<i)) ans=max(ans,(an[x][i]==z?0:an[x][i])),x=f[x][i];
if (x==y) return ans;
for (int i=log2(dep[x]);i>=0;i--)
if (f[x][i]!=f[y][i]) ans=max(max(an[x][i],an[y][i])==z?0:max(an[x][i],an[y][i]),ans),x=f[x][i],y=f[y][i];
return max(max(an[x][0],an[y][0])==z?0:max(an[x][0],an[y][0]),ans);
}然而如果是严格次小生成树，那么，就不能把删去的边与新添加进去的边的值相等。这是问题一。
90分：
int lca(int x,int y,int z){
if (find(x)!=find(y)) return -1;
if (dep[x]<dep[y]) swap(x,y);
int d=dep[x]-dep[y],ans=0;
for (int i=0;(1<<i)<=d;i++)
if ((1<<i)&d) ans=max(ans,(an[x][i]==z?0:an[x][i])),x=f[x][i];
if (x==y) return ans;
for (int i=log2(dep[x]);i>=0;i--)
if (f[x][i]!=f[y][i]) ans=max(max(an[x][i],an[y][i])==z?0:max(an[x][i],an[y][i]),ans),x=f[x][i],y=f[y][i];
return max(max(an[x][0],an[y][0])==z?0:max(an[x][0],an[y][0]),ans);
}第二个问题是，你会发现，在第二段代码里面，我对于与加入边相等的值相等的边，我是不会取的，而是取了0，然而这很明显有问题，所以要存一下次小的值……，于是就改好了！
100分：
int lca(int x,int y,int z){
// if (find(x)!=find(y)) return -1;
if (dep[x]<dep[y]) swap(x,y);
int d=dep[x]-dep[y],ans=0;
for (int i=0;(1<<i)<=d;i++)
if ((1<<i)&d) ans=max(ans,(an[x][i]==z?an1[x][i]:an[x][i])),x=f[x][i];
if (x==y) return ans;
for (int i=log2(dep[x]);i>=0;i--)
if (f[x][i]!=f[y][i]) ans=max(max(an[x][i],an[y][i])==z?an1[x][i]:max(an[x][i],an[y][i]),ans),x=f[x][i],y=f[y][i];
return (max(max(an[x][0],an[y][0])==z?max(max(an1[x][0],an1[y][0]),ans):max(an[x][0],an[y][0]),ans));
}总代吗：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000001,M=600001,INF=1e9+7;
struct st{
int x,y,z;
}kr[M];
int n,m,k,rt,cnt,q,ans=INF,anz;
int nxt[M<<1],last[N],a[M<<1],w[M<<1];
int fa[N],f[N][21],dep[N],sz[N],an[N][21],an1[N][21];
bool l[N];
void add(int x,int y,int z){
nxt[++k]=last[x];
last[x]=k;
a[k]=y;
w[k]=z;
}
bool cmp(st a,st b){
return a.z<b.z;
}
int find(int x){
if (x==fa[x]) return x;
else return fa[x]=find(fa[x]);
}
void kruskal(){
sort(kr+1,kr+1+m,cmp);
for (int i=1;i<=m;i++){
if (kr[i].x==kr[i-1].x&&kr[i].y==kr[i-1].y){l[i]=1;continue;}
int b=find(kr[i].x),c=find(kr[i].y);
if (b!=c){
fa[b]=c;
cnt++;l[i]=1;anz+=kr[i].z;//printf("%d %d %d\n",kr[i].x,kr[i].y,kr[i].z);
add(kr[i].x,kr[i].y,kr[i].z);
add(kr[i].y,kr[i].x,kr[i].z);
}
if (cnt==n-1) return ;
}
}
void dfs_lca(int x,int fa,int y){
dep[x]=dep[fa]+1;
f[x][0]=fa;an[x][0]=y;an1[x][0]=0;
for (int i=1;(1<<i)<=dep[x];i++)
f[x][i]=f[f[x][i-1]][i-1],
an[x][i]=max(an[f[x][i-1]][i-1],an[x][i-1]),
an1[x][i]=max(max(an1[f[x][i-1]][i-1],an1[x][i-1]),an[x][i-1]==an[f[x][i-1]][i-1]?0:min(an[x][i-1],an[f[x][i-1]][i-1]));
for (int i=last[x];i;i=nxt[i])
if (a[i]!=fa) dfs_lca(a[i],x,w[i]);
}
int lca(int x,int y,int z){
// if (find(x)!=find(y)) return -1;
if (dep[x]<dep[y]) swap(x,y);
int d=dep[x]-dep[y],ans=0;
for (int i=0;(1<<i)<=d;i++)
if ((1<<i)&d) ans=max(ans,(an[x][i]==z?an1[x][i]:an[x][i])),x=f[x][i];
if (x==y) return ans;
for (int i=log2(dep[x]);i>=0;i--)
if (f[x][i]!=f[y][i]) ans=max(max(an[x][i],an[y][i])==z?an1[x][i]:max(an[x][i],an[y][i]),ans),x=f[x][i],y=f[y][i];
return (max(max(an[x][0],an[y][0])==z?max(max(an1[x][0],an1[y][0]),ans):max(an[x][0],an[y][0]),ans));
}
signed main(){
// freopen("a.in","r",stdin);
scanf("%lld%lld",&n,&m);
for (int i=1;i<=n;i++) fa[i]=i;
// memset(an,0,sizeof(an));memset(l,0,sizeof(l));
for (int i=1;i<=m;i++) scanf("%lld%lld%lld",&kr[i].x,&kr[i].y,&kr[i].z);
kruskal();
for (int i=1;i<=n;i++)
if (!dep[i]) dfs_lca(i,0,0);
for (int x,i=1;i<=m;i++)
if (!l[i]){
x=lca(kr[i].x,kr[i].y,kr[i].z);//printf("%d %d %d\n",kr[i].x,kr[i].y,x);
if (kr[i].z-x) ans=min(ans,kr[i].z-x);
}
printf("%lld",ans+anz);
return 0;
}