cf609e Minimum spanning tree for each edge
有一个 \(n\) 个顶点,\(m\) 条边的带权无向图 .
对于图上的每一条边,求含有边 \((u,v)\) 的最小生成树大小 .
\(1\leq n\leq 2\cdot 10^5,n-1\leq m\leq 2\cdot 10^5,1\leq u_i,v_i\leq n,u_i\not=v_i,1\leq w_i\leq 10^9\)
这是我们学校信息特长生考试的原题,但是我由于代码能力太烂,考试的时候并没有做出来. qwq
可以对于整个图先求出一个最小生成树 \(T\) .
对于在 \(T\) 上的边最小生成大小就是 \(T\) 的大小.
对于不在 \(T\) 上的边连上之后就是一个环,那么,这个环上必须要断掉一条边,断掉代价除了当前这条边最大的边 .
那么,可以求出 \(u,v\) 的最小公共祖先 \(r\) ,那么,环就是 \(u\rightarrow r\rightarrow v\rightarrow u\) 样子的,但是 \((v,u)\) 这条边是不可以选的 . 那么,能选的是 \(u\rightarrow r\) , \(v\rightarrow r\) 这两条链 .
因为这题不需要支持动态修改,可以用倍增实现,第一次用倍增维护区间最小值 . OwO 感觉自己又会了一个厉害的东西呢.
其实,可以在求lca的时候同时实现,但是我是单独实现的.
时间复杂度 : \(O(n\log n+m\log n)\)
空间复杂度 : \(O(n\log n)\)
第一次提交 : Accepted
Code
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+10;
int n,m;
int w[200010],fa[200010];
bool tree[200010];
vector<pair<int,int> >e,g[200010];
inline int get_fa(int x){
return fa[x]==x?x:fa[x]=get_fa(fa[x]);
}
inline void merge(int u,int v){
u=get_fa(u);v=get_fa(v);
if(u==v)return;
fa[u]=v;
}
int dep[200010];
int nxt[200010][20],mv[200010][20];
void dfs(int x,int fa){
nxt[x][0]=fa;
for(int i=0;i<(int)g[x].size();i++){
int to=g[x][i].first,id=g[x][i].second;
if(to==fa)continue;
dep[to]=dep[x]+1;
mv[to][0]=w[id];
dfs(to,x);
}
}
void build(){
for(int k=0;k+1<20;k++){
for(int i=0;i<n;i++){
if(nxt[i][k]==-1)nxt[i][k+1]=-1;
else{
nxt[i][k+1]=nxt[nxt[i][k]][k];
mv[i][k+1]=max(mv[i][k],mv[nxt[i][k]][k]);
}
}
}
}
int lca(int u,int v){
if(dep[u]>dep[v])swap(u,v);
for(int k=0;k<20;k++){
if((dep[u]-dep[v])>>k&1){
v=nxt[v][k];
}
}
if(u==v)return u;
for(int k=19;k>=0;k--){
if(nxt[u][k]!=nxt[v][k]){
u=nxt[u][k];
v=nxt[v][k];
}
}
return nxt[u][0];
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie();
cin>>n>>m;
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v>>w[i];
u--;v--;
e.push_back(make_pair(u,v));
}
vector<pair<int,int> >v;
for(int i=0;i<m;i++)v.push_back(make_pair(w[i],i));
sort(v.begin(),v.end());
for(int i=0;i<n;i++)fa[i]=i;
long long ans=0;
for(int i=0;i<m;i++){
int id=v[i].second;
int u=e[id].first,v=e[id].second;
if(get_fa(u)==get_fa(v))continue;
merge(u,v);
ans+=w[id];
tree[id]=true;
g[u].push_back(make_pair(v,id));
g[v].push_back(make_pair(u,id));
}
dfs(0,-1);
build();
for(int i=0;i<m;i++){
if(tree[i]){
cout<<ans<<endl;
continue;
}
int u=e[i].first,v=e[i].second;
int r=lca(u,v);
int tmp=0;
for(int k=19;k>=0;k--){
if(nxt[u][k]==-1)continue;
if(dep[nxt[u][k]]>=dep[r]){
tmp=max(tmp,mv[u][k]);
u=nxt[u][k];
}
}
for(int k=19;k>=0;k--){
if(nxt[v][k]==-1)continue;
if(dep[nxt[v][k]]>=dep[r]){
tmp=max(tmp,mv[v][k]);
v=nxt[v][k];
}
}
cout<<ans-tmp+w[i]<<endl;
}
return 0;
}