传染病控制

P1041 [NOIP2003 提高组] 传染病控制

小h注意到了吗？题目背景说，没有靠谱的多项式解法。

小h数据很水。

小h那么今天就来讲讲玄学。

对于这种图论的题目，用vector存图再方便不过了。

虽然看似比链式前向星效率低，其实考虑stl内部有各种优化，反而有时候比数组还快。

存完图，题目中说1是传染源，那么把1当作根节点，搜索求出每个节点的父亲、深度和以该节点为根的子树大小。

以上是树形结构几乎都要求的东西。接下来进入玄学部分。

首先，定义vector int v[n]，v（i）代表深度为i的所有节点。接下来开始深度优先搜索。dfs（d，k）代表已经搜到深度d了，还有k个人是易感人群或传染源。定义bool类型的visit数组，代表是否已切断传播途径。如果i节点的传播途径已经切断，则i为根的子树都不可能被感染了。于是就每一层都在易感人群中选一个切断传播途径，然后k减去那个子树的人数，搜索下一层，再回溯。如果层数已经是最深了，就更新ans，返回。如果某一层没有易感人群了，也更新ans，返回。

看起来没有什么问题，但是又无法证明。可能数据强一点会挂。

小h这是一个远古的题。

小h不过既然说了玄学能过，那就越玄学越好啊。现在不可能出这种题目了，但是也不排除能用玄学骗分的，比如方差和今年noionline的第二题。

小h这道题用以上思路，过了。

正解#include<bits/stdc++.h> defineN 1003 using namespace std; vector<int> G[N],v[N]; bool visit[N]; int n,m,fa[N],dep[N],siz[N],mx,ans; void dfs1(int u=1,int dd=0,int deep=1){ fa[u]=dd; dep[u]=deep; siz[u]=1; mx=max(mx,deep+1); for(vector<int>::iterator it=G[u].begin();it!=G[u].end();++it) if(*it!=dd){ dfs1(*it,u,deep+1); siz[u]+=siz[*it]; } } void dfs(int d=2,int k=n){ if(d==mx){ ans=min(ans,k); return; } vector<int>::iterator it; bool flag(true); for(it=v[d].begin();it!=v[d].end();++it) if(visit[fa[*it]]) visit[*it]=true; else{ visit[*it]=false; flag=false; } if(flag){ ans=min(ans,k); return; } for(it=v[d].begin();it!=v[d].end();++it) if(!visit[*it]){ visit[*it]=true; dfs(d+1,k-siz[*it]); visit[*it]=false; } } int main(){ //freopen("1.in","r",stdin); scanf("%d%d",&n,&m); ans=n; int i,j,k; for(i=0;i<m;i++){ scanf("%d%d",&j,&k); G[j].push_back(k); G[k].push_back(j); } dfs1(); for(i=1;i<=n;i++) v[dep[i]].push_back(i); dfs(); return printf("%d\n",ans)&0; }

小h