静态树上最大/最小边权
题目链接:CF609E Minimum spanning tree for each edge(最大边)
题目链接:洛谷 P1967 货车运输(最小边)
CF609E Minimum spanning tree for each edge
题目大意:
给你 $n$ 个点, $m$ 条边,对于每一条边,求出包含当前边的最小生成树的边权和
思路解析:
我们首先可以想到我们可以跑出原图的最小生成树,对于我们选择保留的最优边,那么答案肯定是最小生成树的权值和。
那么对于不是最小生成树的边呢?
我们可以发现每当在最小生成树中加入一条边,就一定形成一个环,并且去掉环上任意一条边是不会影响图的连通性。
所以我们有了以下算法:
对于不是树边的边,我们加入当前边并删去加入边后形成的环上权值最大的边。当然我们不是真的加边删边,只需要计算权值相加减就可以。
既然我们有了思路,我们就思考如何实现。我们用Kruskal做生成树并建树连边。
对于求树上简单路径的最大边,我们可以使用 树剖+线段树/倍增 解决
特别的,我们可以把边权转化为点权去维护,就是使用当前点到它父亲节点的边权作为点权去维护
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
int n,m;
int e[maxn],nex[maxn],h[maxn],id;
ll w[maxn],len[maxn],v[maxn];
int dfn[maxn],sz[maxn],fa[maxn],dep[maxn],son[maxn],top[maxn];
int tim;
int f[maxn],st[maxn];
ll sum,ans[maxn];
int find(int x){
if(f[x]==x)return x;
return f[x]=find(f[x]);
}
struct nod{
int x,y;
ll z;
int pos;
}g[maxn];
bool cmp(nod u,nod v){
return u.z<v.z;
}
void add(int x,int y,ll z){
e[++id]=y;
len[id]=z;
nex[id]=h[x];
h[x]=id;
}
void dfs1(int u,int f){
fa[u]=f;
dep[u]=dep[f]+1;
sz[u]=1;
int maxsz=-1;
for(int i=h[u];i;i=nex[i]){
int j=e[i];
if(j==f)continue;
//cout<<u<<"->"<<j<<endl;
v[j]=len[i];
dfs1(j,u);
sz[u]+=sz[j];
if(sz[j]>maxsz){
maxsz=sz[j];
son[u]=j;
}
}
}
void dfs2(int u,int t){
dfn[u]=++tim;
top[u]=t;
w[tim]=v[u];
if(!son[u])return ;
dfs2(son[u],t);
for(int i=h[u];i;i=nex[i]){
int j=e[i];
if(j==fa[u]||j==son[u])continue;
dfs2(j,j);
}
}
struct node{
int l, r;
ll odd;
}tr[maxn];
void pushup(int u)
{
tr[u].odd=max(tr[u<<1].odd,tr[u<<1|1].odd);
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
ll query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
{
return tr[u].odd;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
ll res = -1;
if (l <= mid ) res = max(res,query(u << 1, l, r));
if (r > mid) res =max(res, query(u << 1 | 1, l, r));
return res;
}
}
ll ask(int x,int y){
ll ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=max(ans,query(1,dfn[top[x]],dfn[x]));
x=fa[top[x]];
}
if(x==y)return ans;
if(dep[x]>dep[y])swap(x,y);
ans=max(ans,query(1,dfn[x]+1,dfn[y]));
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++){
int x,y;
ll z;
cin>>x>>y>>z;
g[i]={x,y,z,i};
}
sort(g+1,g+m+1,cmp);
for(int i=1;i<=m;i++){
int x=find(g[i].x),y=find(g[i].y);
if(x==y)continue;
add(g[i].x,g[i].y,g[i].z);
add(g[i].y,g[i].x,g[i].z);
f[y]=x;
sum+=g[i].z;
st[g[i].pos]=1;
}
dfs1(1,1);
dfs2(1,1);
build(1,1,n);
for(int i=1;i<=m;i++){
if(st[g[i].pos]){
ans[g[i].pos]=sum;
continue;
}
ans[g[i].pos]=sum+g[i].z-ask(g[i].x,g[i].y);
}
for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
}
洛谷 P1967 货车运输(最小边)
题目大意:
与上一题有异曲同工之妙
这一题是求图中两点路径之间的最小边权
思路解析:
有了上一题的经验,我们很快就想到,跑最大生成树,然后 树剖+线段树/倍增 维护最小边权(边权转换为点权)
完结撒花(bushi
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
int n,m;
int e[maxn],nex[maxn],h[maxn],id;
ll w[maxn],len[maxn],v[maxn];
int dfn[maxn],sz[maxn],fa[maxn],dep[maxn],son[maxn],top[maxn];
int tim;
int f[maxn],st[maxn];
ll sum,ans[maxn];
int find(int x){
if(f[x]==x)return x;
return f[x]=find(f[x]);
}
struct nod{
int x,y;
ll z;
int pos;
}g[maxn];
bool cmp(nod u,nod v){
return u.z>v.z;
}
void add(int x,int y,ll z){
e[++id]=y;
len[id]=z;
nex[id]=h[x];
h[x]=id;
}
void dfs1(int u,int f){
fa[u]=f;
dep[u]=dep[f]+1;
sz[u]=1;
int maxsz=-1;
for(int i=h[u];i;i=nex[i]){
int j=e[i];
if(j==f)continue;
//cout<<u<<"->"<<j<<endl;
v[j]=len[i];
dfs1(j,u);
sz[u]+=sz[j];
if(sz[j]>maxsz){
maxsz=sz[j];
son[u]=j;
}
}
}
void dfs2(int u,int t){
dfn[u]=++tim;
top[u]=t;
w[tim]=v[u];
if(!son[u])return ;
dfs2(son[u],t);
for(int i=h[u];i;i=nex[i]){
int j=e[i];
if(j==fa[u]||j==son[u])continue;
dfs2(j,j);
}
}
struct node{
int l, r;
ll odd;
}tr[maxn];
void pushup(int u)
{
tr[u].odd=min(tr[u<<1].odd,tr[u<<1|1].odd);
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
ll query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
{
return tr[u].odd;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
ll res = inf;
if (l <= mid ) res = min(res,query(u << 1, l, r));
if (r > mid) res =min(res, query(u << 1 | 1, l, r));
return res;
}
}
ll ask(int x,int y){
ll ans=inf;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=min(ans,query(1,dfn[top[x]],dfn[x]));
x=fa[top[x]];
}
if(x==y)return ans;
if(dep[x]>dep[y])swap(x,y);
ans=min(ans,query(1,dfn[x]+1,dfn[y]));
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++){
int x,y;
ll z;
cin>>x>>y>>z;
g[i]={x,y,z,i};
}
sort(g+1,g+m+1,cmp);
for(int i=1;i<=m;i++){
int x=find(g[i].x),y=find(g[i].y);
if(x==y)continue;
add(g[i].x,g[i].y,g[i].z);
add(g[i].y,g[i].x,g[i].z);
f[y]=x;
sum+=g[i].z;
st[g[i].pos]=1;
}
dfs1(1,1);
dfs2(1,1);
build(1,1,n);
int q;
cin>>q;
while(q--){
int x,y;
cin>>x>>y;
if(find(x)!=find(y)){
cout<<-1<<endl;
continue;
}
cout<<ask(x,y)<<endl;
}
}
马上就去学!
建议用Kruskal重构树更方便也能维护更多东西