CF1108F MST Unification
前言
神说,你需要一颗最小生成树,于是你求出了最小生成树。
神又说,你这生成树不唯一啊,快去改改,于是就有了这篇题解
思路
同 P4180 [BJWC2010] 严格次小生成树 ,先算出最小生成树。
由于要保证树唯一,考虑怎么才可以让其唯一。
回顾 克鲁斯卡尔 算法可以发现,如果有相同长度的边,连接的两个相同的点集,那么这两个边都可选,这就是最小生成树多解的原因。
于是就有了两种方式:
方一
我们考虑将长度相同的边一起处理,具体如下:
- 先将长度相同的边给找出来
- 记录在没有连接这些边的情况下,边两端点集不同的边的边数为 \(cnt\)
- 从前到后连边,如果可以连接则
cnt--
最后 \(ans=\sum cnt\)
方二
直接考虑生成树后树上倍增,对于一条非树边,求得其两端点之间的简单路径上边权的最大值,若与该非树边边权相等,则 ans++
CODE
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef long double ld;
const ll maxn=2e5+2;
inline ll read_int(){
ll a=0;bool f=0;char g=getchar();
while(g<'0'||g>'9') {if(g=='-') f=1;g=getchar();}
while('0'<=g&&g<='9') a=a*10+g-'0',g=getchar();
return f ? -a : a;
}
inline void write(ll a,bool f=1){
char lin[40];ll top=0;
if(a<0) a=-a,putchar('-');
while(a) lin[++top]=a%10+'0',a/=10;
if(!top) lin[++top]='0';
while(top) putchar(lin[top--]);
if(f) putchar('\n');
}
struct SJ{int f,t,v;}sj[maxn];int cnt;
bool operator < (const SJ a,const SJ b){return a.v<b.v;}
struct E{
int t,n;
ll v;
}edge[maxn*2];
int l,head[maxn];
struct BCJ{
int bcj[maxn];
inline void neww(int n){
for(int i=1;i<=n;i++) bcj[i]=i;
}
inline int find(int s){return (s==bcj[s] ? s : (bcj[s]=find(bcj[s])));}
inline void add(int a,int b){
bcj[find(a)]=find(b);
}
inline bool link(int a,int b){return find(a)==find(b);}
}bcj;
int n,m;
ll bz[maxn][21],point[maxn][21],dep[maxn];
inline void dfs(int s,int f,int W){
bz[s][0]=W,point[s][0]=f;
dep[s]=dep[f]+1;
for(int i=1;i<=20;i++){
bz[s][i]=max(bz[s][i-1],bz[point[s][i-1]][i-1]);
point[s][i]=point[point[s][i-1]][i-1];
}
for(int i=head[s];i;i=edge[i].n){
int t=edge[i].t;
if(t==f) continue;
dfs(t,s,edge[i].v);
}
}
inline int upto(ll &ans,int s,int C){
for(int i=20;~i;i--){
if((1<<i)&C) ans=max(ans,bz[s][i]),s=point[s][i];
}
return s;
}
inline int LCA_max(int a,int b){
ll ans=0;
if(dep[a]>dep[b]) swap(a,b);
b=upto(ans,b,dep[b]-dep[a]);
if(a==b) return ans;
for(int i=20;~i;i--){
if(point[a][i]==point[b][i]) continue;
ans=max(ans,max(bz[a][i],bz[b][i]));
a=point[a][i],b=point[b][i];
}
return max(ans,max(bz[a][0],bz[b][0]));
}
inline void read(){
n=read_int(),m=read_int();
for(int i=1;i<=m;i++){
sj[i].f=read_int(),sj[i].t=read_int(),sj[i].v=read_int();
if(sj[i].f==sj[i].t){i--,m--;}
}
bcj.neww(n);
sort(sj+1,sj+1+m);
for(int i=1;i<=m;i++){
if(bcj.link(sj[i].f,sj[i].t)){sj[++cnt]=sj[i];continue;}
l++,edge[l]=(E){sj[i].t,head[sj[i].f],sj[i].v},head[sj[i].f]=l;
l++,edge[l]=(E){sj[i].f,head[sj[i].t],sj[i].v},head[sj[i].t]=l;
bcj.add(sj[i].f,sj[i].t);
}
dfs(1,1,0);
int ans=0;
for(int i=1;i<=cnt;i++){
ans+=(LCA_max(sj[i].f,sj[i].t)==sj[i].v);
}
write(ans);
}
int main (){
// freopen(".in","r",stdin);
read();
// while(1) getchar();
}