P5680 [GZOI2017] 共享单车 题解

· · 题解

题目传送门

前置知识

最短路 | 最近公共祖先 | 虚树

解法

题目中所说的 回收路线树 即以 k 为根节点的最短路径树，可以使用 Dijkstra 构建。

标记 回收区域 本质上是对 回收区域 构建虚树，然后就和 luogu P2495 [SDOI2011] 消耗战 基本一致了，根据儿子节点的 投放 状态进行树形 DP 转移。

注意本题中虚树上两点边权为原最短路径树上两点间的距离。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
struct node
{
    int nxt,to,w;
}e[200010];
int head[50010],dis[50010],vis[50010],fa[50010],siz[50010],son[50010],dep[50010],top[50010],dfn[50010],a[50010],f[50010],tot=0,cnt=0;
pair<int,int>pre[50010];
void add(int u,int v,int w)
{
    cnt++;
    e[cnt].nxt=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}
void dijkstra(int k)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue<pair<int,int> >q;
    q.push(make_pair(0,k));
    dis[k]=0;
    while(q.empty()==0)
    {
        int x=q.top().second;
        q.pop();
        if(vis[x]==0)
        {
            vis[x]=1;
            for(int i=head[x];i!=0;i=e[i].nxt)
            {
                if(dis[e[i].to]==0x3f3f3f3f||dis[e[i].to]>dis[x]+e[i].w)
                {
                    dis[e[i].to]=dis[x]+e[i].w;
                    pre[e[i].to]=make_pair(x,e[i].w);
                    q.push(make_pair(-dis[e[i].to],e[i].to));
                }   
                else
                {
                    if(dis[e[i].to]==dis[x]+e[i].w&&pre[e[i].to].first>x)
                    {
                        pre[e[i].to]=make_pair(x,e[i].w);
                    }
                }
            }
        }
    }
}
void dfs1(int x,int father)
{
    tot++;
    dfn[x]=tot;
    siz[x]=1;
    fa[x]=father;
    dep[x]=dep[father]+1;
    for(int i=head[x];i!=0;i=e[i].nxt)
    {
        dis[e[i].to]=dis[x]+e[i].w;
        dfs1(e[i].to,x);
        siz[x]+=siz[e[i].to];
        son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x];
    }
}
void dfs2(int x,int id)
{
    top[x]=id;
    if(son[x]!=0)
    {
        dfs2(son[x],id);
        for(int i=head[x];i!=0;i=e[i].nxt)
        {
            if(e[i].to!=son[x])
            {
                dfs2(e[i].to,e[i].to);
            }
        }
    }
}
int lca(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]>dep[top[v]])
        {
            u=fa[top[u]];
        }
        else
        {
            v=fa[top[v]];
        }
    }
    return dep[u]<dep[v]?u:v;
}
int get_dis(int x,int rt)
{
    return dis[x]-dis[rt];
}
bool cmp(int a,int b)
{
    return dfn[a]<dfn[b];
}
struct Vitrual_Tree
{
    vector<int>g[50010];
    stack<int>s;
    void build(int len,int k)
    {
        sort(a+1,a+1+len,cmp);
        while(s.empty()==0)
        {
            s.pop();
        }
        s.push(k);
        g[k].clear();
        for(int i=1;i<=len;i++)
        {
            int rt=lca(a[i],s.top());
            while(s.top()!=rt)
            {
                int tmp=s.top();
                s.pop();
                if(dfn[s.top()]<dfn[rt])
                {
                    s.push(rt);
                    g[rt].clear();
                }
                g[s.top()].push_back(tmp);
            }
            s.push(a[i]);
            g[a[i]].clear();
        }
        while(s.top()!=k)
        {
            int tmp=s.top();
            s.pop();
            g[s.top()].push_back(tmp);
        }
    }
    void dfs(int x)
    {
        f[x]=0;
        for(int i=0;i<g[x].size();i++)
        {
            dfs(g[x][i]);
            f[x]+=(vis[g[x][i]]==1)?get_dis(g[x][i],x):min(get_dis(g[x][i],x),f[g[x][i]]);
        }
    }
}V;
int main()
{
// #define Isaac
#ifdef Isaac
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    int n,m,q,k,u,v,w,i,j;
    cin>>n>>m>>k>>q;
    for(i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dijkstra(k);
    cnt=0;
    memset(e,0,sizeof(e));
    memset(head,0,sizeof(head));
    for(i=1;i<=n;i++)
    {
        if(i!=k)
        {
            add(pre[i].first,i,pre[i].second);
        }
    }
    dfs1(k,0);
    dfs2(k,k);
    memset(vis,0,sizeof(vis));
    for(j=1;j<=q;j++)
    {
        cin>>u>>m;
        if(u==0)
        {
            for(i=1;i<=m;i++)
            {
                cin>>a[i];
                vis[a[i]]^=1;
            }
        }
        else
        {
            for(i=1;i<=m;i++)
            {
                cin>>a[i];
            }
            V.build(m,k);
            V.dfs(k);
            cout<<((f[k]==0)?-1:f[k])<<endl;
        }
    }
    return 0;
}