题解 P1041 【传染病控制】
Plus_Ultra · · 题解
一. 题目大意
-
这个题目意思是给我们一棵树，按照每个点到根节点的距离分层（到1号点）.
-
每一层里面可以砍掉一条边，砍完这条边之后，这个边连接的子节点所在的子树就全部安全了.
-
在最多砍 n 条边的情况下，问我们不安全的节点最少有多少个.
二. 错误做法
-
很多人接触到这道题目就会想到一种贪心做法，直接选这一层内子树最大的节点删掉即可.
-
但是这种做法是错误的.
-
因为这个题目不满足 局部最优解 = 全局最优解 的性质.
-
在函数上表示就是一个多峰函数，而不是单峰函数.
-
当然可以得到一部分分.
-
经同学要求举了一个反例：
三. 具体思路
我们看一下数据范围: n <=300,所以这棵树最多只有300层（一条链），就可以用大暴搜了qwq!!!
-
建树.这个没啥好说的qwq.
-
预处理出来每个节点的深度，记录每一层节点.
-
预处理出来子树大小.
-
从第一层节点开始DFS，枚举下一层的节点，分别把这条相连的边剪掉，把整个子树标记为已经控制，DFS下一层，回溯时更新答案即可.
注意：如果某一层的边全部剪掉的话，那么就到达不了下一层了，即为最终状态，直接更新 ans 即可.
四. 代码
下面是代码：
#include<iostream>
#define N 310
using namespace std;
int count[N],deep[N][N],vis[N];
int n,p,maxx,ans=310;
struct Node
{
int num,son[N];
}tree[N];
void Deep(int x,int dp)
{
maxx=max(maxx,dp);//记录最深层
for(int i=1;i<=tree[x].num;i++)
{
int y=tree[x].son[i];
deep[dp][++deep[dp][0]]=y;//记录当层节点
Deep(y,dp+1);//下一层
}
}
int Size(int x)
{
if(!tree[x].num) return 1;//子树大小为一
for(int i=1;i<=tree[x].num;i++)
count[x]+=Size(tree[x].son[i]);//加上大小
return count[x];
}
void Cover(int x,int y)//y=1为已经安全，0则为还有危险
{
vis[x]=y;//标记
for(int i=1;i<=tree[x].num;i++)
Cover(tree[x].son[i],y);
}
void DFS(int now,int per)
{
if(now==maxx)
{
ans=min(ans,per);
return;
}//更新答案
int vi=0;
for(int i=1;i<=deep[now][0];i++)
{
int x=deep[now][i];
if(vis[x])//已经安全
{
vi++;continue;
}
Cover(x,1);
DFS(now+1,per-count[x]);
Cover(x,0);//回溯
}
if(vi==deep[now][0]) ans=min(ans,per);
}
int main()
{
cin>>n>>p;int x,y;
for(int i=1;i<=n;i++) count[i]=1;
for(int i=1;i<=p;i++)
{
cin>>x>>y;
if(x>y) swap(x,y);
tree[x].son[++tree[x].num]=y;
}//建树
Deep(1,2);
Size(1);
DFS(2,n);
cout<<ans<<endl;
return 0;
}如果觉得有帮助的话别忘了给可爱的up主三连点赞哦qwq.
Update on 2019.10.25 举了反例，希望管理员给过.