题解：P5680 [GZOI2017] 共享单车

MioNeko0207 · 2024-08-08 10:25:57 · 题解

前置知识

• Dijkstra 求最短路径树

• 树形 DP

• 虚树 （帮你 OI-Wiki 一下）

题意简述

其它题解其实写的相当详尽了，概括一下就是：

• 求无向图的最短路径树（注意路径长度相同时按编号排序）。

• 有两种操作：0 表示将标记取反，1 表示求代价。

思路

• Dijkstra 求最短路径树

• 异或完成取反操作

• 建虚树跑树形 DP 求代价

  • 关于虚树

    • 构造一棵可爱的虚树

      这里采用的是二次排序 + LCA 连边的方式。

      1. 将回收区域（关键点）第一次按 dfn 序排序

      2. 插入关键点的 LCA，此处采用倍增求 LCA

      3. 将关键点和它们的 LCA 合在一起第二次按 dfn 序排序，去重以得到虚树的所有点编号

      4. 将虚树的点连边

    • 在可爱的虚树上跑树形 DP 即可，方法和普通树形 DP 一样

  • 关于 DP 式

    我们通过题意分两种情况进行 DP。此处设节点 u 为节点 v 的父亲节点，求节点 u 处的 DP 值。

    • 被标记时：必须阻断这条路径，代价为 dis[v]-dis[u]，即 u 到 v 的路径长度。

    • 无标记时：有下列两种情况，取二者中的较小值作为 u 的 DP 值。

      • 选择截断该路径，使得 u 与以 v 为根子树不连通，这种情况代价同被标记时。

      • 选择让 v 之后的节点自行截断，这种情况代价为 dfs(v)。

Code

觉得难理解的可以看看这篇含详细注释的代码 awa。

#include<bits/stdc++.h>
using namespace std;
const int N=50010,M=100010,MAXN=50010;

int n,m,k,q;
int val[N];//记录是否被标记 
bool flag;//记录是否找到被标记投放区域 
int r[MAXN],num;//r回收区域编号 
int h[N],to[M<<1],len[M<<1],nxt[M<<1],cnt;//链式前向星

void addedge(int u,int v,int l)//建边 
{
    cnt++;
    nxt[cnt]=h[u];
    h[u]=cnt;
    to[cnt]=v;
    len[cnt]=l;
}

int pre[N],Len[N];//pre[i]记录节点i的前一个节点 Len[i]记录i和pre[i]的距离，方便之后重利用之前的链式前向星
int dis[N];//Dijkstra中当前最短距离 

void Find_Tree()//Dijkstra求以k为根的最小路径树 
{
    memset(dis,-1,sizeof(dis));
    priority_queue<pair<int,int>> q;//Dijkstra堆优化 
    //记得priority_queue默认大根堆，求最小路径树可以插入路径长度的相反数 
    q.push(make_pair(0,k));
    dis[k]=0;
    while(!q.empty())
    {
        int d=-q.top().first,u=q.top().second;
        q.pop();
        for(int i=h[u];i;i=nxt[i])
        {
            int v=to[i];
            if(dis[v]==-1||dis[v]>dis[u]+len[i])//取路径长度较短
            {
                pre[v]=u;
                Len[v]=len[i];
                dis[v]=dis[u]+len[i];
                q.push(make_pair(-dis[v],v));
            }
            else if(dis[v]==dis[u]+len[i]&&pre[v]>u)//路径长度相同取编号较小
            {
                pre[v]=u;
                Len[v]=len[i];
            }
        }
    }
    //清空原来的链式前向星，用于记录新的最小路径树 
    memset(h,0,sizeof(h));
    cnt=0;
    for(int i=1;i<=n;i++)
        if(i!=k)
        {
            addedge(pre[i],i,Len[i]);
            addedge(i,pre[i],Len[i]);
        }
}

int dfn[N],DFN;//时间戳 
int dep[N],f[N][16];//dep[i]记录节点i在树上深度 f记录祖先 

void dfs(int u,int fa){//LCA预处理 
    dfn[u]=++DFN;//同时记录时间戳 
    dep[u]=dep[fa]+1;
    for(int i=1;i<=15;i++) f[u][i]=f[f[u][i-1]][i-1];
    for(int i=h[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==fa) continue;
        f[v][0]=u;
        dfs(v,u);
    }
}

int lca(int x,int y){//求x和y的LCA 
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=15;i>=0;i--)
    {
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
        if(x==y) return y;
    }
    for(int i=15;i>=0;i--)
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    return f[x][0];
}

//虚树点数为 实点+虚点 数组要开两倍 
int vt[MAXN<<1],vtcnt;//vt存储虚树中的点 vtcnt虚树节点个数 
vector<int> VT[MAXN<<1];//VT vector存虚树 

bool cmp(int a,int b){ return dfn[a]<dfn[b]; }//根据 dfn 序排序 

void Virtual_Tree()//建虚树 
{
    vtcnt=0;
    sort(r+1,r+1+num,cmp);//第一次排序 
    for(int i=1;i<num;i++)
    {
        vt[++vtcnt]=r[i];
        vt[++vtcnt]=lca(r[i],r[i+1]);//插入LCA 
    }
    vt[++vtcnt]=r[num];
    sort(vt+1,vt+1+vtcnt,cmp);//第二次排序 
    vtcnt=unique(vt+1,vt+1+vtcnt)-vt-1;//去重 
    for(int i=1;i<vtcnt;i++)
    {
        int l=lca(vt[i],vt[i+1]);
        VT[l].push_back(vt[i+1]);//连边 
    }
}

int calc(int u)//虚树上跑树形DP求最小代价 
{
    int res=0;
    if(val[u]) flag=1;
    int siz=VT[u].size();
    for(int i=0;i<siz;i++)
    {
        int v=VT[u][i];
        int tmp=calc(v);
        if(val[v]) res+=dis[v]-dis[u];//被标记时必须阻断这条路径
        else res+=min(dis[v]-dis[u],tmp);//无标记时选择截断该路径或继承 v 的 DP 值 
    }
    VT[u].clear();
    return res;
}

int main()
{
    cin>>n>>m>>k>>q;
    for(int i=1;i<=m;i++)
    {
        int u,v,l;
        scanf("%d%d%d",&u,&v,&l);
        addedge(u,v,l);
        addedge(v,u,l);
    }
    Find_Tree();
    dfs(k,0);
    while(q--)
    {
        int opt;
        scanf("%d%d",&opt,&num);
        if(!opt)//opt==0 区域标记异或取反 
        {
            for(int i=1;i<=num;i++)
            {
                int p;
                scanf("%d",&p);
                val[p]^=1;
            }
        }
        else//opt==1 建虚树 + DP
        {
            for(int i=1;i<=num;i++) scanf("%d",&r[i]);
            r[++num]=k;
            Virtual_Tree();
            flag=0;
            int ans=calc(k);
            if(flag) printf("%d\n",ans);
            else printf("-1\n");
        }
    }
    return 0;
}

Tips：撰文不易，不适轻喷。