【题解】P13078 [NOISG 2019] Rigged Roads

题意

给定一个

N

个节点

E

条边的无向图，你需要给每条边设定一个权值，所有边的权值需要形成一个

1\sim E

的排列，并且这个图分配权值后的最小生成树为一棵给定的生成树，求字典序最小的分配边权的方案。

解法

由于是字典序最小，所以考虑贪心地处理。从

1

至

E

地枚举每条边，并考虑给其分配最小的边权。我们定义生成树上的边为关键边，则根据每条边是否为关键边可以进行如下分讨：

为关键边：分配一个未分配的最小边权即可。
不为关键边：设这条边连接 $u$ 和 $v$ ，则生成树上 $u$ 到 $v$ 的路径上边权最大的边的边权需小于这条边的边权。不妨暴力地给生成树上这条路径地边分配边权，边的编号越小边权越小即可。

但是显然暴力分配边权会超时，发现一条边只能被分配一次边权，而每次分配边权都可以拆分为

u\to lca

和

v\to lca

两条路径，每条路径只需考虑其祖先，所以设

fa_u

为节点

u

的祖先节点中深度最大的没有点配边权的节点（生成树上的边权可以下放为点权），更新后令

fa_u

变为

u

的父节点，使用并查集维护即可。

时间复杂度

O(N+E\log N)

，瓶颈在于找 LCA。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
class DSU //并查集
{
    private:
        int fa[N];
    public:
        int find(int u)
        {
            if(fa[u]==u)return u;
            return fa[u]=find(fa[u]);
        }
        void init(){for(int i=1;i<N;i++)fa[i]=i;}
        void update(int u,int v){fa[find(u)]=v;}
}dsu;
struct edge{int v,w;};
vector<edge>e[N];
void build(int u,int v,int w){e[u].emplace_back((edge){v,w});}
int fa[N],dep[N],siz[N],son[N],num[N];
void get_fa(int u,int f)
{
    fa[u]=f,dep[u]=dep[f]+1,siz[u]=1;
    for(auto i:e[u])
    {
        int v=i.v,w=i.w;
        if(v==f)continue;
        num[v]=w,get_fa(v,u),siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
int top[N];
void get_top(int u,int tp)
{
    top[u]=tp;
    if(son[u])get_top(son[u],tp);
    for(auto i:e[u])
        if(i.v!=son[u]&&i.v!=fa[u])get_top(i.v,i.v);
}
int LCA(int u,int v) //树链剖分求 LCA
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    return u;
}
int now;
int ans[N];
vector<int>arr;
void get_arr(int u,int aim) //将所有需要分配边权的边存到 arr 中
{
    while(dep[u]>aim)
    {
        int nxt=dsu.find(u);
        if(dep[nxt]<=aim)break;
        arr.emplace_back(num[nxt]);
        u=nxt,dsu.update(u,fa[u]);
    }
}
bool typ[N];
int u[N],v[N];
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>u[i]>>v[i];
    for(int i=1,a;i<n;i++)cin>>a,typ[a]=true,build(u[a],v[a],a),build(v[a],u[a],a);
    dsu.init();
    get_fa(1,0),get_top(1,1);
    for(int i=1;i<=m;i++)
    {
        if(ans[i])continue;
        if(!typ[i])
        {
            int lca=LCA(u[i],v[i]);
            get_arr(u[i],dep[lca]),get_arr(v[i],dep[lca]);
            sort(arr.begin(),arr.end());
            for(int i:arr)ans[i]=++now; //分配边权
            arr.clear();
        }
        ans[i]=++now;
        if(typ[i])
        {
            if(dep[u[i]]>dep[v[i]])swap(u[i],v[i]);
            dsu.update(v[i],u[i]);
        }
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<' ';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _=1;
    for(;_;_--)solve();
    return 0;
}

【题解】P13078 [NOISG 2019] Rigged Roads

文章操作

题意

解法

代码

相关推荐

评论

【题解】P13078 [NOISG 2019] Rigged Roads