一个网的路
xieyikai2333 · · 题解
- 题目传送门
闲话
- 赛时爆肝 T2，结果 T2 是个紫的没打出来，然后这题没时间了，打了个
20 分的暴力滚蛋了。
解题思路
-
显然，我们先进行操作 1 再进行操作 2 一定不劣，否则操作 2 连上去的边可能又被炸掉。
-
考虑把森林炸成若干链，然后连起来，显然如果我们炸了
x 条边，那么操作 2 的次数可以表示为(n-1)-(m-x) 。于是我们只要使炸掉的边数（x ）+炸掉的点数（操作 1 的次数）最小即可。 -
考虑对于每个无根树随便取个根进行树形DP。
状态设计
- 设
dp_{i,0/1/2} 表示i 的子树已经被炸成若干链了且\begin{cases} \text{这个点被炸了} &0\\ \text{这个点没有被炸，它的儿子有 1 个连着它} &1\\ \text{这个点没有被炸，它的儿子有 2 个连着它} &2 \end{cases}
状态转移
-
约定：记
son_u 为点u 的儿子集合，d_u 为点u 的度数，FIR_{sth} 是一类数中的最大值，SEC_{sth} 是一类数中的次大值。 -
对于状态
0 ：- 转移方程：
dp_{u,0}=\sum_{v \in son_{u}} \min\{dp_{v,0}-1,dp_{v,2}\}+d_{u}+1 - 解释说明：
- 如果一个点被炸掉，那么它的子树无论何种情况都可以转移。
- 之所以
dp_{v,0} 要减去1 是因为如果u 和v 都炸它们之间的边被重复计算了。 - 之所以不用考虑
dp_{v,1} ，是因为dp_{v,1} 一定大于dp_{v,2} ，原因由后面会给出的dp_{v,2} 的转移方程可知。 - 加上
d_{u} 是因为又炸了d_{u} 条边，加上1 是因为又炸了一个点
- 转移方程：
-
对于状态
1 ：- 转移方程：
dp_{u,1}=(\sum_{v \in son_{u}} dp_{v,0})-\max\{0,FIR_{v \in son_{u}}(dp_{v,0}-dp_{v,1})\} - 解释说明：
- 由定义，
u 的儿子最多有一个不被炸，所以最多有一个儿子状态可以是1 其他都必须被炸。
- 由定义，
- 转移方程：
-
对于状态
2 ：- 转移方程：
dp_{u,2}=dp_{i,1}-\max\{0,SEC_{v \in son_{u}}(dp_{v,0}-dp_{v,1})\} - 解释说明：
- 由定义，
u 的儿子最多有两个不被炸。在有一个不被炸的基础上再减去第二大的即可。
- 由定义，
- 由转移方程可知，
dp_{u,2} \lt dp_{u,1} 显然成立。
- 转移方程：
最终答案
- 约定：
ANS 是最终答案，root 是每棵树的根节点组成的集合。
至于为什么不用管
代码实现
好像没什么要注意的细节。。。
AC 代码：
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int dp[N][3];
bool vis[N];
vector<int> nodes[N];
void dfs(int u)
{
vis[u]=true;
int fir=0,sec=0;
for(int v:nodes[u])
{
if(vis[v])continue;
dfs(v);
int delta=dp[v][0]-dp[v][1];
if(delta>fir)sec=fir,fir=delta;
else if(delta>sec)sec=delta;
dp[u][0]+=min(dp[v][0]-1,dp[v][2]);
dp[u][1]+=dp[v][0];
}
dp[u][0]+=nodes[u].size()+1;
dp[u][1]-=fir;
dp[u][2]=dp[u][1]-sec;
return;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
int ans=(n-1)-m;
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d %d",&u,&v);
nodes[u].push_back(v);
nodes[v].push_back(u);
}
for(int i=1;i<=n;i++)if(!vis[i])dfs(i),ans+=min(dp[i][0],dp[i][2]);
printf("%d",ans);
return 0;
}