居然A了，我也是吓尿了
//版权所有 HBat
//^_^
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdlib>

using namespace std;

int layerB_A[301];//层地址 ----------> layerB_A[x]=y;表示节点x在y层，储存节点的层地址，方便建立层列表（层地图）
vector < vector <int> >layer(301);//层列表（层地图） ----------> layer[x][y]=z;表示第x层第y+1个节点是z
bool layeruse[301];//层中可用元素
int sum = 1;//生病人数
int minsum = 999999;//生病人数最小值
int n, p;

struct tree//树
{
int fr;
vector <int>ch;
}trap[301];

void dfslayer(int node)//建层地址
{
layerB_A[node] = layerB_A[trap[node].fr] + 1;//layerB_A[x]=y;表示节点x在y层，储存节点的层地址，方便建立层列表（层地图）
int i, len;
len = trap[node].ch.size();
for (i = 0; i<len; ++i)
dfslayer(trap[node].ch[i]);
return;
}

int dfsclose(int node)//标记节点不可用
{
layeruse[node] = true;
int i, len;
len = trap[node].ch.size();
for (i = 0; i < len; ++i)
dfsclose(trap[node].ch[i]);
return 0;
}

int dfsopen(int node)//标记节点可用
{
layeruse[node] = false;
int i, len;
len = trap[node].ch.size();
for (i = 0; i < len; ++i)
dfsopen(trap[node].ch[i]);
return 0;
}

inline int rale(int la)//计算本次生病人数
{
int i, len = layer[la].size();
int a = len;
for (i = 0; i < len; ++i)
if (layeruse[layer[la][i]])--a;
return a;
}

inline void makelayer()//建层列表（层地图）
{
layerB_A[0] = 0;
dfslayer(1);
layerB_A[0] = -1;
int i;
for (i = 1; i <= n; ++i)
layer[layerB_A[i]].push_back(i);
return;
}

int dfs(int node)//node为层数
{
int x, i, len, k, maxn = -1, no = -1;
bool key = true;//不一定只有len==0时才完成任务，当子层中所有节点都移除时也完成任务，用key标记key==true为完成任务
len = layer[node].size();//node层的大小
if (len == 0)//判断是否搜到底
{
minsum = minsum < sum ? minsum : sum;//完成一次后保存最小生病人数
return 0;
}
for (i = 0; i < len; ++i)//先贪心一下，找到感染人数最多的节点，记录为no
{
if (layeruse[layer[node][i]])continue;//判断该节点是否被移出树
x = trap[layer[node][i]].ch.size();
if (maxn < x)
{
maxn = trap[layer[node][i]].ch.size();
no = layer[node][i];
}
}
if (no != -1)//如果贪心到的话，优先搜索
{
dfsclose(no);
k = rale(node);
sum += k;
dfs(1 + node);
sum -= k;
dfsopen(no);
}
for (i = 0; i < len; ++i)//搜索回溯
{
if (layeruse[layer[node][i]] || layer[node][i] == no)continue;
key = false;//不一定只有len==0时才完成任务，当子层中所有节点都移除时也完成任务，key==false为没有完成任务
dfsclose(layer[node][i]);
k = rale(node);
sum += k;
if (sum>minsum)//剪枝
{
sum -= k;
dfsopen(layer[node][i]);
return 0;
}
dfs(1 + node);
// minsum = minsum<sum ? minsum : sum;//**************************************************************************
sum -= k;
dfsopen(layer[node][i]);
}
if (key)//判断不是树的底层的时候，是否完成任务
minsum = minsum < sum ? minsum : sum;
return 0;
}

int main()
{
int i, x, y;
memset(layerB_A, -1, sizeof(layerB_A));
cin >> n >> p;
for (i = 1; i <= p; ++i)
{
cin >> x >> y;
if (x != 1 && trap[x].fr == 0)//建树，除1节点外，父节点为0的为被感染节点。这里输入时，父节点和子节点的前后输入顺序不一
{
trap[x].fr = y;
trap[y].ch.push_back(x);
}
else
{
trap[y].fr = x;
trap[x].ch.push_back(y);
}
}
makelayer();//建层，用来做搜索的地图
dfs(2);//搜索
cout << minsum;
//system("pause");
return 0;
}

说的是给定一棵树，结果输入的都是无向边，为此WA了两次。
首先dfs把无向图转有向图，然后再搜索。
搜索非常裸，每次枚举砍掉A里面的哪个点，然后把剩下的点能到达的所有点存进B里面，再dfsB。
```c++
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

const int INF = 1000000000;
const int maxn = 300 + 10;

int n, m;
int acc[maxn][maxn];
vector<int> G[maxn];

void dfs (int u, int f) {
for (int v = 0; v < n; v++) if (acc[u][v] && v != f) {
G[u].push_back(v);
dfs(v, u);
}
}

int dfs (const vector<int>& A) {
int l = A.size();
if (!l) return 0;
int ans = INF;
vector<int> B;
for (int i = 0; i < l; i++) { //cut i
B.clear();
for (int j = 0; j < l; j++) if (j != i) {
int u = A[j];
for (int k = 0; k < G[u].size(); k++) B.push_back(G[u][k]);
}
ans = min(ans, dfs(B));
}
return ans + l - 1;
}

int main () {
cin >> n >> m;

while (m--) {
int u, v;
cin >> u >> v; u--; v--;
acc[u][v] = acc[v][u] = 1;
}

dfs(0, -1);

vector<int> A;
for (int i = 0; i < G[0].size(); i++)
A.push_back(G[0][i]);

cout << dfs(A)+1;
return 0;
}
```

cheat cheat 200以上加入随机化，200以下敲最优化剪枝+暴搜
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<ctime>
#include<cstdlib>
int depth[330];
int dmax(0),ans(0x7fffff);
struct point{
int x,y;
};
std::vector<int> edge[330];
std::vector<point> dep[310];
bool inq[330];
std::queue<int> q;
using namespace std;
void dfs1(int depth1,int f)
{
if(f+dmax-depth1>ans)
return ;
if(depth1==dmax)
if(f<ans)
ans=f;
int s;
int sie=f;
bool v[dep[depth1].size()];
memset(v,0,sizeof(v));
for(int i=0;i<dep[depth1].size()%50;)
{
int h=rand()%dep[depth1].size();
if(!v[h])
{
v[h]=true;
i++;
}
else continue;
sie=f;
for(int j=0;j<dep[depth1].size();j++)
{
if(h!=j && inq[dep[depth1][j].x])
{
inq[dep[depth1][j].y]=true;
sie++;
}
}
dfs1(depth1+1,sie);
for(int j=0;j<dep[depth1].size();j++)
inq[dep[depth1][j].y]=false;
}
return ;
}void dfs(int depth1,int f)
{
if(f+dmax-depth1>ans)
return ;
if(depth1==dmax)
if(f<ans)
ans=f;
int s;
int sie=f;
for(int i=0;i<dep[depth1].size();i++)
{
sie=f;
for(int j=0;j<dep[depth1].size();j++)
{
if(i!=j && inq[dep[depth1][j].x])
{
inq[dep[depth1][j].y]=true;
sie++;
}
}
dfs(depth1+1,sie);
for(int j=0;j<dep[depth1].size();j++)
inq[dep[depth1][j].y]=false;
}
return ;
}
void bfs1()
{
int s;
while(!q.empty())
{
s=q.front();
q.pop();
for(int i=0;i<edge[s].size();i++)
if(!inq[edge[s][i]])
{
inq[edge[s][i]]=true;
if(depth[s]+1>dmax)
dmax=depth[s]+1;
depth[edge[s][i]]=depth[s]+1;
q.push(edge[s][i]);
dep[depth[s]].push_back((point){s,edge[s][i]});
}
}
}
int main()
{
srand(888888);
int n,p,f,t;
scanf("%d%d",&n,&p);
for(int i=0;i<p;i++)
{
scanf("%d%d",&f,&t);
edge[f].push_back(t);
edge[t].push_back(f);
}
ans=n;
depth[1]=1;
q.push(1);
memset(inq,0,sizeof(inq));
inq[1]=true;
bfs1();
q.push(1);
memset(inq,0,sizeof(inq));
inq[1]=true;
if(n>=200)
dfs1(1,1);
else dfs(1,1);
printf("%d",ans);
}

非常丑陋的按层dfs....写了好久而且又长又乱

#include<stdio.h>
#define MAXVALUE 10000000
int org[301][301];
int tree[301][301];
int n,p;
int maxdepth=-1;
int sonnum[301]={0};
int boolsDFS[301]={0};
int min=MAXVALUE;

void buildtree(int k,int depth)
{
int i;

for(i=1;i<=n;i++)
{
if(i>k && org[k][i]==1)
{
tree[depth+1][i]=k;
sonnum[depth+1]++;
if(depth+1>maxdepth) maxdepth=depth+1;
buildtree(i,depth+1);
}
}
}

void DFS(int deep,int now)
{

if(now>min) return;

int i,sum=0,flag=0;

for(i=1;sum<sonnum[deep];i++)
{

if(tree[deep][i]!=0)
{
sum++;
if(boolsDFS[tree[deep][i]]==1) boolsDFS[i]=1;
else boolsDFS[i]=0;

if(boolsDFS[i]==0) {now++;flag=1;}
}
}

if(flag==0)
{
if(now<min) min=now;
goto maxlabel;
}

sum=0;

for(i=1;sum<sonnum[deep];i++)
{
if(tree[deep][i]!=0)
{
sum++;

if(boolsDFS[i]==0)
{
boolsDFS[i]=1;
now--;
if(deep!=maxdepth) DFS(deep+1,now);
else if(now<min) min=now;

boolsDFS[i]=0;
now++;
}
}
}

maxlabel:return;

}

int main( )
{

int x1,x2;
int i,j;

scanf("%d %d",&n,&p);

for(i=0;i<=300;i++)
for(j=0;j<=300;j++)
{
org[i][j]=0;
tree[i][j]=0;
}

for(i=1;i<=p;i++)
{
scanf("%d %d",&x1,&x2);
org[x1][x2]=1;
org[x2][x1]=1;
}

buildtree(1,1);

DFS(2,1);

printf("%d",min);

return 0;
}

const oo=maxlongint shr 1;
var ToT,Ans,i,j,k,l,m,n:Longint;
A:array[1..300,1..300] of Boolean;
Bo:array[1..300] of Boolean;
F:array[1..300] of Longint;
Child:array[1..300,0..300] of Longint;

Procedure Build_Tree(X:Longint);
var i,j,k:Longint;
Begin
For i:=1 to N do
If (Not bo[i])and(A[X,i]) then
Begin
Inc(Child[X,0]);
Child[X,Child[X,0]]:=i;
Bo[i]:=True;
Build_Tree(i);
End;
End;

Procedure Search(X:Longint);
var i,j,k,Tmp:Longint;
Bo:Boolean;
Begin
If ToT>Ans then Exit;
Bo:=False;Tmp:=ToT;
For i:=1 to N do
If F[i]=X then
For j:=1 to Child[i,0] do
Begin
F[Child[i,j]]:=X+1;
Inc(ToT);
Bo:=True;
End;
Dec(ToT);
For i:=1 to N do
If F[i]=X+1 then
Begin
F[i]:=0;
Search(X+1);
F[i]:=X+1;
End;
ToT:=Tmp;
For i:=1 to N do If F[i]=X+1 then F[i]:=0;
If Not Bo then If ToT<Ans then Ans:=ToT;
End;

Begin
Readln(N,M);
For i:=1 to M do
Begin
Readln(j,k);
A[j,k]:=True;A[k,j]:=True;
End;
Bo[1]:=True;
Build_Tree(1);
Fillchar(Bo,sizeof(Bo),False);
Bo[1]:=True;F[1]:=1;
Ans:=oo;ToT:=1;
Search(1);
Writeln(Ans);
End.

宽搜有3个点莫名其妙的错误

深搜竟然能AC。。。

编译通过...

├ 测试数据 01：答案正确... (461ms, 756KB)

├ 测试数据 02：答案正确... (55ms, 756KB)

├ 测试数据 03：答案正确... (35ms, 756KB)

├ 测试数据 04：答案正确... (47ms, 756KB)

├ 测试数据 05：答案正确... (67ms, 756KB)

├ 测试数据 06：答案正确... (0ms, 756KB)

├ 测试数据 07：答案正确... (16ms, 756KB)

├ 测试数据 08：答案正确... (32ms, 756KB)

├ 测试数据 09：答案正确... (67ms, 756KB)

├ 测试数据 10：答案正确... (379ms, 756KB)

type arr=array[0..300] of integer;

var tr:array[1..300] of arr;

n:integer;

min:longint;

procedure init;

var i,m,a,b,t:longint;

begin

min:=maxlongint;

readln(n,m);

for i:=1 to m do begin

readln(a,b);

if a>b then begin

t:=a;

a:=b;

b:=t;

end;

inc(tr[a,0]);

tr[a,tr[a,0]]:=b;

end;

end;

procedure go(h:longint; g:arr);

var g2:arr;

i,j,k:longint;

begin

if g[0]=0 then begin

if min>h then min:=h;

exit;

end;

for i:=1 to g[0] do begin

fillchar(g2,sizeof(g2),0);

for j:=1 to g[0] do

if ji then begin

for k:=1 to tr[g[j],0] do begin

inc(g2[0]);

g2[g2[0]]:=tr[g[j],k];

end;

end;

if h+g[0]-1

第9点部分贪心算法不过的原因是两棵子树，一棵可能拥有的节点多，但是如果另外一棵在往下几层难切的话，是应该选择切后者的。

例如：节点1和节点6同一代，1与2，3，4，5相连

6~11成链状，如果贪心先切多节点的6，最终会有4人感染（1，3，4，5）

而先切一，只会有2人感染（6，7）

这题我一个同学用了随机化，也可以过。

随记选取某层中某条边被删除就行了。