洛谷 P1041 noip2003 传染病控制

题目：传染病控制

思路：
搜索。
先预处理出每个点的深度。
然后对于每一层，枚举割掉的子边，向下一层搜索。
注意单支树的情况。

代码：

#include<bits/stdc++.h>
using namespace std;#define maxn 300
#define read(x) scanf("%d",&x)int n;vector<int> g[maxn+5];
int sz[maxn+5],d[maxn+5],f[maxn+5];vector<int> dist[maxn+5];void dfs(int x,int fa) {
    d[x]=d[fa]+1,f[x]=fa;dist[d[x]].push_back(x);if(g[x].size()==1&&x!=1) {
    sz[x]=1;return;}for(int i=0; i<g[x].size(); i++) {
    int y=g[x][i];if(y==fa) continue;dfs(y,x);sz[x]+=sz[y];}return ;
}bool isuse[maxn+5];
int s=(1<<30);void find(int x,int w) {
    if(w>=s) return ;if(dist[x].size()==0) {
    s=min(s,w);return ;}for(int i=0; i<dist[x].size(); i++) {
    int y=dist[x][i];if(isuse[y]) {
    for(int j=0; j<g[y].size(); j++) {
    if(g[y][j]!=f[y]) isuse[g[y][j]]=true;}}}bool flg=0;for(int i=0; i<dist[x].size(); i++) {
    int y=dist[x][i];if(isuse[y]) continue;flg=true;for(int j=0; j<g[y].size(); j++) {
    if(g[y][j]!=f[y]) isuse[g[y][j]]=true;}int ans=0;for(int j=0; j<dist[x].size(); j++) {
    if(isuse[dist[x][j]]||i==j) continue;ans++;}find(x+1,w+ans);for(int j=0; j<g[y].size(); j++) {
    if(g[y][j]!=f[y]) isuse[g[y][j]]=false;}}for(int i=0; i<dist[x].size(); i++) {
    int y=dist[x][i];if(isuse[y]) {
    for(int j=0; j<g[y].size(); j++) {
    if(g[y][j]!=f[y]) isuse[g[y][j]]=false;}}}if(flg==0) s=min(s,w);
}int main() {
    read(n);read(n);n++;for(int i=1; i<n; i++) {
    int x,y;read(x),read(y);g[x].push_back(y);g[y].push_back(x);}dfs(1,0);find(2,0);printf("%d",s+1);return 0;
}