题解：P5680 [GZOI2017] 共享单车

· · 题解

反复读完题后我们终于知道了要干什么：

建树，建虚树，求最值。

建树：在原图跑单源最短路，转移时特判距离相同取编号小者，并记录每个点从哪个点转移过来，最后找出最短路构成的树。

建虚树：回收区域是关键点，应拿它们建虚树，边权就是它们在回收路线上的距离。

求最值：用 dp 求，设有节点 x，其子节点为 y，若 y 被标记，这条路一定要被阻断，x 的费用加上 v_{x,y}；否则可断可不断，x 的费用加上 v_{x,y} 与 y 的费用的最小值。

代码：

#include<bits/stdc++.h>
#define rd read()
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ll long long
#define pb push_back
#define mkp make_pair
#define for_(a,b,c) for(int a=b;a<=c;++a)
#define For_(a,b,c) for(int a=b;a>=c;--a)
using namespace std;
int n,m,S,Q,H;
const int N=4e5+10;
vector<pair<int,int>>vv[N],v[N],e[N];
struct node{
    int x,d;
};
priority_queue<node>q;
bool operator<(const node A,const node B){
    return A.d>B.d;
}
ll dis[N],id[N];
bool vis[N];
void dij() {
    memset(dis,0x3f,sizeof(dis));
    dis[S]=0;
    q.push({S,0});
    while(!q.empty()) {
        node h=q.top();
        q.pop();
        int x=h.x;
        if(vis[x])continue;
        vis[x]=1;
        for(auto h:vv[x]){
            int y=h.first,val=h.second;
            ll s=dis[x]+val;
            if(s<dis[y]){
                dis[y]=s;
                id[y]=x;
                q.push({y,dis[y]});
            }
            else if(s==dis[y]){
                id[y]=min(id[y],x);
            }
        }
    }
}
int st[N],tp;
ll P(ll x,ll y){
    return x*N+y;
}
unordered_map<ll,bool>mp;
int dep[N],dfn[N],td,f[N][30];
void dfs_LCA(int x){
    dfn[x]=++td;
    for(auto h:v[x]){
        int y=h.first,val=h.second;
        dep[y]=dep[x]+1;
        f[y][0]=x;
        dfs_LCA(y);
    }
}
int LCA(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    For_(i,H,0)if(dep[f[x][i]]>=dep[y])x=f[x][i];
    if(x==y)return x;
    For_(i,H,0)if(f[x][i]^f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
int num;
int k[N];
bool cmp(int x,int y){
    return dfn[x]<dfn[y];
}
int a[N],tot;
int in[N];
int cntin;
bool flag;
ll DP(int x){
    if(in[x])flag=1;
    ll fx=0;
    for(auto h:e[x]){
        ll y=h.first,val=h.second;
        ll fy=DP(y);
        if(in[y])fx+=val;
        else fx+=min(val,fy);
    }
    e[x].clear();
    return fx;
}
void work(){
    k[++num]=S;
    sort(k+1,k+1+num,cmp);
    tot=0;
    for_(i,1,num-1) {
        a[++tot]=k[i];
        a[++tot]=LCA(k[i],k[i+1]);
    }
    a[++tot]=k[num];
    sort(a+1,a+1+tot,cmp);
    tot=unique(a+1,a+1+tot)-a-1;
    for_(i,1,tot-1) {
        int x=a[i],y=a[i+1];
        int L=LCA(x,y);
        e[L].pb(mkp(y,dis[y]-dis[L]));
    }
    flag=0;
    ll fS=DP(S);
    if(flag)cout<<fS<<"\n";
    else cout<<-1<<"\n";
}
inline ll read(){ll d=0,f=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch<='9'&&ch>='0'){d=(d<<1)+(d<<3)+ch-'0';ch=getchar();}return f?-d:d;}
int main(){
    n=rd,m=rd,S=rd,Q=rd;H=__lg(n)+1;
    for_(i,1,m){
        int x=rd,y=rd,val=rd;
        vv[x].pb(mkp(y,val));
        vv[y].pb(mkp(x,val));
    }
    dij();
    for_(i,1,n){
        int cur=i;
        while(cur){
            st[++tp]=cur;
            cur=id[cur];
        }
        for_(j,1,tp-1){
            int x=st[j],y=st[j+1];
            if(mp.find(P(min(x,y),max(x,y)))!=mp.end())break;
            mp[P(min(x,y),max(x,y))]=1;
            v[y].pb(mkp(x,dis[x]-dis[y]));
        }
        tp=0;
    }
    dep[S]=1;
    dfs_LCA(S);
    for_(j,1,H)for_(i,1,n)f[i][j]=f[f[i][j-1]][j-1];
    while(Q--){
        int op=rd;
        if(!op)For_(i,rd,1)in[rd]^=1;
        else{
            num=rd;
            for_(i,1,num)k[i]=rd;
            work();
        }
    }

    return 0;
}