题解：洛谷P1041 [NOIP2003 提高组] 传染病控制

感觉我题解越写越水（？？？

受不了，博主开始写错题题解了。。。

洛谷

---

思路

虽然看到了一坨DP和随机化解法但是不如dfs！

你看那小小的 $n$ 小小的（只有 $300$），所以爆搜甚至不用剪枝

感觉思路也不是非常非常非常困难，dfs算一下最多的不被感染人数再用总数减一下即可

代码

#include<bits/stdc++.h>

using namespace std;

struct node
{
	int u,v;
}a[1005];
int head[1005];
int tot;

int dep[1005],chd[1006],par[1005]; //深度，子节点数，父节点 
int cnd[1005]; //i深度下的第几个点 
int cnt[1005][1005]; //深度为i的第j个点 
bool vis[1005]; //是否感染（0为是，1为否）
//这里是因为在感染时考虑一个点如果未被感染，它的子节点不会被感染，求出最大不感染数 

void add(int u,int v) //链式前向星建图 
{
	a[++tot].u=head[u];
	head[u]=tot;
	a[tot].v=v;
}

void getc(int u,int f,int d) //预处理深度子节点和父节点 
{
	dep[u]=d;
	chd[u]=1;
	par[u]=f;
	
	for(int i=head[u];i;i=a[i].u) //直接dfs 
	{
		int v=a[i].v;
		if(v==f)
		{
			continue;
		}
		getc(v,u,d+1);
		chd[u]+=chd[v];
	}
}

void dfs(int u,bool f) //通过dfs来进行不感染或还原（f为1不感染，f为0还原） 
{
	for(int i=head[u];i;i=a[i].u)
	{
		int v=a[i].v;
		vis[v]=f;
		
		if(v==par[u])
		{
			continue;
		}
		
		dfs(v,f);
	}
}

int ans,ans1;

void solve(int d) //算出最多的不感染数 
{	
	for(int i=1;i<=cnd[d];i++) //循环每一个深度 
	{
		if(vis[par[cnt[d][i]]]==1)
		{
			continue;
		}
		
		dfs(cnt[d][i],1); //以该深度的第i个点往下不感染 
		ans+=chd[cnt[d][i]];
		solve(d+1); //下一层 
		ans-=chd[cnt[d][i]]; //还原 
		dfs(cnt[d][i],0);

	}
	
    ans1=max(ans,ans1);
	
}

int n,p;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin>>n>>p;

	for(int i=1;i<=p;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v),add(v,u);
	}

	getc(1,0,1);
	for(int i=1;i<=n;i++)
	{
		cnt[dep[i]][++cnd[dep[i]]]=i;
	} //预处理 
	
	solve(2); //从第二层开始循环 
	
	cout<<n-ans1<<"\n";

	return 0;
}

---

发现泄题解还是很水。。。