传染病控制(暴力搜索)

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#define N 307
#define INF 0x3f3f3f
using namespace std;
inline int read() {
	int x=0,f=1; char ch=getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	return x * f;
}
int n,cnt,mxdep,ans=INF;
int head[N],fth[N],sz[N],vis[N];
int deep[N][N];
struct Edge {
	int next,to;
}edge[N<<1];
inline void add(int u,int v) {
	edge[++cnt].next = head[u];
	edge[cnt].to = v;
	head[u] = cnt;
}
void Dfs_first(int u,int fa,int dep) {
	mxdep = max(mxdep,dep);
	sz[u] = 1; fth[u] = fa; deep[dep][++deep[dep][0]] = u;
	for(int i=head[u];i;i=edge[i].next) {
		int v = edge[i].to;
		if(v==fa) continue;
		Dfs_first(v,u,dep+1); sz[u] += sz[v]; 
	}
}
void make_mark(int u,int tag) {
	vis[u] = tag;
	for(int i=head[u];i;i=edge[i].next) {
		int v = edge[i].to;
		if(v!=fth[u]) make_mark(v,tag);
	}
}
void Dfs(int dep,int tot) {	//从2开始搜 
	if(dep==mxdep+1) {
		ans = min(ans,tot); return ;
	}
	int flag = 0;
	for(int i=1;i<=deep[dep][0];++i) {
		if(vis[deep[dep][i]]) {
			++flag; continue;
		}
		make_mark(deep[dep][i],1);
		Dfs(dep+1,tot-sz[deep[dep][i]]);
		make_mark(deep[dep][i],0);
	}
	if(flag==deep[dep][0]) ans = min(ans,tot);
}
int main()
{
	n = read(); int m = read();
	for(int i=1,u,v;i<=m;++i) {
		u = read(), v = read();
		add(u,v), add(v,u);
	}
	Dfs_first(1,0,1);
	Dfs(2,n);
	printf("%d
",ans);
//    printf("

test

 maxdep=%d",mxdep);
	return 0;
}