【CodeForces 609E】 Minimum spanning tree for each edge

题意很清楚,给定一张带权无向图,对于图上的每一条边,询问包括这一条边的生成树中边权权值之和最小的。

首先想到的方法是每次都先把要求的这条边加入最小生成树,然后跑一遍 Kruskal,但用膝盖想一下都知道这样肯定是会 T 飞的,所以我们可以直接在原来的最小生成树上进行修改,也就是说,把这一条边强行塞进最小生成树,由于这样很明显会形成一个环,所以我们还需要从这个环里再删掉一条边。

假设此时这条边连接的是uuvv 两个点,则从uuvv 的最短路径应该会经过LCA(u,v)\text{LCA}(u,v),所以这个环应该是从uuLCA(u,v)\text{LCA}(u,v) 再到vv 最后回到uu,因此,我们需要删掉的边应该是在从uuLCA(u,v)\text{LCA}(u,v) 再到vv 这条路径上,又因为要求新的最小生成树的权值和最小,所以我们应该尽量删掉权值较大的边。

因此,这道题就变成了先求出最小生成树,然后对于每一条边,询问其两个端点在树上的最短路径中边权最大的边。

这种问题本来可以用树剖做,但由于没有修改操作,不需要那么麻烦其实就是懒,使用倍增求 LCA,在求每个点的第2i2^i 个父亲的时候,另外开一个数组,求每个点到它第2i2^i 个父亲这条路径上最大的边权,然后在往上跳的时候顺便用一个变量统计一下就可以了,具体的看代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
#define pll pair<long long,long long>
using namespace std;
struct Edge
{
long long u;
long long v;
long long c;
long long id;
};
bool cmp(Edge a,Edge b)
{
return a.c<b.c;
}
bool cmp2(Edge a,Edge b)//这个是求完最小生成树后还原所有边的顺序的,虽然也可以再开一个数组,但是我懒。
{
return a.id<b.id;
}
Edge a[200001];
vector<pll> edge[200001];
long long n,m,cnt,k,log2n,f[200001],dep[200001],fa[200001][21],maxn[200001][21];
long long find(long long x)
{
return f[x]==x? f[x]:f[x]=find(f[x]);
}
void dfs(long long u,long long father)
{
fa[u][0]=father;
dep[u]=dep[father]+1;
for(long long i=1;(1<<i)<=dep[u];i++)
{
fa[u][i]=fa[fa[u][i-1]][i-1];
maxn[u][i]=max(maxn[u][i-1],maxn[fa[u][i-1]][i-1]);//求 u 到它第 2^i 个父亲这条路径上最大的边权。
}
for(long long i=0;i<edge[u].size();i++)
{
long long v=edge[u][i].first,c=edge[u][i].second;
if(v!=father)
{
maxn[v][0]=c;//在搜索儿子前先把这个初始化一下。
dfs(v,u);
}
}
}
long long lca(long long u,long long v)
{
long long depu=dep[u],depv=dep[v],ans=0;//ans 用来统计最大边权。
if(depu!=depv)
{
if(depu<depv)
{
swap(depu,depv);
swap(u,v);
}
for(long long i=0;(1<<i)<=depu-depv;i++)
if((depu-depv)&(1<<i))
{
ans=max(ans,maxn[u][i]);
u=fa[u][i];
}
}
if(u==v)
return ans;
for(long long i=log2n;i>=0;i--)
if(fa[u][i]!=fa[v][i])
{
ans=max(ans,max(maxn[u][i],maxn[v][i]));
u=fa[u][i];
v=fa[v][i];
}
return max(ans,max(maxn[u][0],maxn[v][0]));
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++)
f[i]=i;
for(long long i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&a[i].u,&a[i].v,&a[i].c);
a[i].id=i;
}
sort(a+1,a+1+m,cmp);
for(long long i=1;i<=m;i++)//Kruskal 求最小生成树。
{
long long t1=find(a[i].u),t2=find(a[i].v);
if(t1!=t2)
{
f[t1]=t2;
cnt++;
k+=a[i].c;
edge[a[i].u].push_back(mp(a[i].v,a[i].c));
edge[a[i].v].push_back(mp(a[i].u,a[i].c));
}
if(cnt==n-1)
break;
}
sort(a+1,a+1+m,cmp2);
log2n=log(n)/log(2)+0.5;
dfs(1,0);
for(long long i=1;i<=m;i++)
printf("%lld\n",k+a[i].c-lca(a[i].u,a[i].v));//加上当前这条的边权,删去路径上最大的边权。
return 0;
}

一开始的时候我还想着要不要判断一下这条边是否是树边,但其实如果是树边的话,那么加上的也是它,删去的也是它,根本没有发生变化,所以没必要特判。

另外,这道题一定要开 long long,因为109×210510^9\times 2\cdot10^5 很明显炸 int 了。

【CodeForces 609E】 Minimum spanning tree for each edge

http://www.azusemisa.top/posts/3582173013.html

作者

AzuSemisa

发布于

2020-08-10

更新于

2020-08-23

许可协议

评论