题目分析
出题人是擅长隐藏题意的
建树
首先给你一张无向图，然后指定一个根节点 \(k\)，从根节点开始沿最短路到每一个节点。如果到某个节点有多条最短路径，选择上一个节点编号最短的。
考虑记录前驱的 Dijkstra。
namespace DJ
{
int dis[maxn], pre[maxn], val[maxn], vis[maxn];
priority_queue<pair<int, int>> pq;
void Dijkstra(int s)
{
memset(dis, 0x3f, sizeof dis);
dis[s]=0;
pre[s]=0;
pq.emplace(0, s);
while(!pq.empty())
{
auto [d, u]=pq.top();
pq.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto [v, w]:e[u])
{
if(dis[u]+w<dis[v])
{
dis[v]=dis[u]+w;
pre[v]=u;
val[v]=w;
pq.emplace(-dis[v], v);
}
else if(dis[u]+w==dis[v])
pre[v]=min(pre[v], u),
val[v]=w;
}
}
}
void search(int x) // 记录路径
{
while(vis[x]&&pre[x])
{
e[pre[x]].emplace_back(x, val[x]);
vis[x]=0;
x=pre[x];
}
}
}
询问
首先用 \(tag_i\) 记录第 \(i\) 个点是否为投放区域。
对于 0 操作，就是翻转点的标记。
if(op==0)
for(int i=1, t;i<=num;i++)
cin>>t, tag[t]^=1;
对于 1 操作，题目说的很清楚，先以 \(k\) 和询问点建一棵虚树。
前置知识：虚树。
d.clear();
d.push_back(k);
for(int i=1, t;i<=num;i++)
cin>>t, d.emplace_back(t);
sort(d.begin(), d.end(), cmp);
for(int i=1;i<=num;i++)
d.push_back(LCA(d[i], d[i-1]));
sort(d.begin(), d.end(), cmp);
auto end_it=unique(d.begin(), d.end());
for(auto it=d.begin()+1;it!=end_it;it++)
{
int lc=LCA(*(it-1), *it);
g[lc].emplace_back(*it, dis[*it]-dis[lc]);
}
然后要求让根节点和每个有标记的节点均不连通，所以考虑虚树上树形dp。
令 \(dp_u\) 表示虚树上使 \(u\) 与以 \(u\) 为根的子树中的关键点断开的最小代价。
易得转移方程：
如果 \(tag_v=1\)，那么它对 \(dp_u\) 的贡献为 \(\operatorname{dis}(u, v)\)。
如果 \(tag_v=0\)，那么它对 \(dp_u\) 的贡献为 \(\min(\operatorname{dis}(u, v), dp_v)\)。
int dp(int x)
{
int ret=0;
for(auto [v, w]:g[x])
{
int f=dp(v);
if(tag[v]) ret+=w;
else ret+=min(w, f);
}
g[x].clear();
return ret;
}
因为边权不为 \(0\)，所以如果 dp 的结果为 \(0\)，那么就证明没有被标记的投放区域，特判一下，输出 -1。
Code
#include<bits/stdc++.h>
using namespace std;
#define maxn 50004
vector<pair<int, int>> e[maxn], g[maxn];
namespace DJ
{
int dis[maxn], pre[maxn], val[maxn], vis[maxn];
priority_queue<pair<int, int>> pq;
void Dijkstra(int s)
{
memset(dis, 0x3f, sizeof dis);
dis[s]=0;
pre[s]=0;
pq.emplace(0, s);
while(!pq.empty())
{
auto [d, u]=pq.top();
pq.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto [v, w]:e[u])
{
if(dis[u]+w<dis[v])
{
dis[v]=dis[u]+w;
pre[v]=u;
val[v]=w;
pq.emplace(-dis[v], v);
}
else if(dis[u]+w==dis[v])
pre[v]=min(pre[v], u),
val[v]=w;
}
}
}
void search(int x)
{
while(vis[x]&&pre[x])
{
e[pre[x]].emplace_back(x, val[x]);
vis[x]=0;
x=pre[x];
}
}
}
namespace slpf
{
int son[maxn], fa[maxn], siz[maxn], dep[maxn], dis[maxn];
void dfs1(int u, int f)
{
fa[u]=f;
siz[u]=1;
dep[u]=dep[f]+1;
for(auto [v, w]:e[u])
if(v!=f)
{
dis[v]=dis[u]+w;
dfs1(v, u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
int top[maxn], dfn[maxn];
void dfs2(int u, int t)
{
dfn[u]=++*dfn;
top[u]=t;
if(!son[u]) return;
dfs2(son[u], t);
for(auto [v, w]:e[u])
if(!dfn[v])
dfs2(v, v);
}
int LCA(int x, int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x, y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
}
using slpf::dfn;
using slpf::dis;
using slpf::LCA;
int tag[maxn];
vector<int> d;
int dp(int x)
{
int ret=0;
for(auto [v, w]:g[x])
{
int f=dp(v);
if(tag[v]) ret+=w;
else ret+=min(w, f);
}
g[x].clear();
return ret;
}
int main()
{
int n, m, k, q;
cin>>n>>m>>k>>q;
for(int i=1, u, v, w;i<=m;i++)
{
cin>>u>>v>>w;
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
}
DJ::Dijkstra(k);
for(int i=1;i<=n;i++) e[i].clear();
for(int i=1;i<=n;i++) DJ::search(i);
auto cmp=[&](int a, int b){return dfn[a]<dfn[b];};
slpf::dfs1(k, 0);
slpf::dfs2(k, k);
while(q--)
{
int op, num;
cin>>op>>num;
if(op==0)
for(int i=1, t;i<=num;i++)
cin>>t, tag[t]^=1;
else
{
d.clear();
d.push_back(k);
for(int i=1, t;i<=num;i++)
cin>>t, d.emplace_back(t);
sort(d.begin(), d.end(), cmp);
for(int i=1;i<=num;i++)
d.push_back(LCA(d[i], d[i-1]));
sort(d.begin(), d.end(), cmp);
auto end_it=unique(d.begin(), d.end());
for(auto it=d.begin()+1;it!=end_it;it++)
{
int lc=LCA(*(it-1), *it);
g[lc].emplace_back(*it, dis[*it]-dis[lc]);
}
int otp=dp(k);
cout<<(otp?otp:-1)<<'\n';
}
}
}