历史遗留问题
luogu1041 传染病控制
S1
这题我记得去年NOIP之前就开始做？然后想不出来宣告放弃了？
妈耶，看来我今年还是这么菜。干脆AFO算了。
看题看题。
对于这个题目的“切断传播途径”，我们可以看做在每一层选择一个点，删除掉这个点的子树，使得最后删除掉的人最多。
首先我们看这个题后效性极其严重，显然不是树形DP。我们从搜索的角度考虑一下。
这里有个思路： 先BFS处理出每一层都有哪些节点，之后一层一层往下搜，每一层枚举删掉哪个点，之后再把删掉的点和有标记的点的儿子打上标记，下一层不选有标记的点。
这样理性分析是可以过掉大部分的点的，但最坏情况下应该是有那么两到四个点不过。那我们该怎么办？
考虑剪枝。
剪枝：这个感觉可行性剪枝不太会有，我们用一个最优性剪枝。在每一层的开始，我们都先判断当前感染人数是否大于Ans，如果是的话直接退出即可。
记忆化似乎不是很可搞的样子。因为它本质上还是一种DP，而这个的后效性太强了。因为这一层能选哪些与上一层删掉了什么息息相关，把这一路记忆下来不就和没记忆一个样么……回溯处理什么的还是别想了，有可能这个题正着SB爆搜就能过呢……
感觉这下得有80了？
S2
还是觉得不太稳妥，这个方法要么是想复杂了，要么是还有啥没想到。
感觉自己现在差不多就这个水平了……
想了这么久都没想到更好的方案，比赛的时候估计就得打这个了吧……
打着打着发现自己之前的思路还有个漏洞……真是没谁了，那种一层一层打标记的操作实现起来就知道是不可取的，反倒还必须得一次性把这个人的孩子都打上标记……
感觉好GG啊。
S3
我艹！90pts！没T！
下个样例看看！
发现一个漏洞：我是等到搜到最后一层再结算，但是有可能直接一下子都砍掉了，就到不了最后一层。
还有一个小BUG：如果结算的时候当前这一层已经全部被救治，那就不用减一，这个小特判一下就行了。
大意了……
过了，xin吧xin吧。
最BT的就是这个我预测复杂度要爆炸的程序还跑了0ms……
代码
#include<iostream>
#include<cstdio>
#include<cctype>
#include<queue>
#define N 301
#define Big (1000000000 + 10)
using namespace std;
int ans,Mx,n,m,Flor[N][N],num[N],K[N],head[N<<1],dis[N],cnt;
bool vis[N];
queue<int> q;
struct node {
int next,to;
}E[N<<1];
void Add(int x,int y) {
E[++cnt].next=head[x];
E[cnt].to=y;
head[x]=cnt;
}
int Max(int x,int y) {
if (x>y) return x;
return y;
}
int read() {
char c=getchar();
int r=0,f=1;
while (!isdigit(c)) {
if (c=='-') f=-1;
c=getchar();
}
while (isdigit(c)) {
r=(r*10)+(c^48);
c=getchar();
}
return r*f;
}
void Bfs() {
q.push(1); dis[1]=1;
while (!q.empty()) {
int x=q.front(),d=dis[x]; q.pop();
Flor[d][++num[d]]=x;
for (int i=head[x];i;i=E[i].next) {
int y=E[i].to;
if (!dis[y]) {
q.push(y);
dis[y]=dis[x]+1;
Mx=max(Mx,dis[y]);
}
}
}
for (int i=1;i<=Mx;i++) K[i]=num[i];
}
void Colr(int x) {
for (int i=head[x];i;i=E[i].next) {
int y=E[i].to;
if (dis[y]==dis[x]+1) {
vis[y]=1;
K[dis[y]]--;
Colr(y);
}
}
}
void iColr(int x) {
for (int i=head[x];i;i=E[i].next) {
int y=E[i].to;
if (dis[y]==dis[x]+1) {
vis[y]=0;
K[dis[y]]++;
iColr(y);
}
}
}
void Dfs(int dep,int Sum) {
if (Sum+Max(K[dep]-1,0)>=ans) return;
if (dep==Mx) {
ans=Sum+Max(K[dep]-1,0);
return;
}
bool flag=0;
for (int i=1;i<=num[dep];i++) {
int x=Flor[dep][i];
if (vis[x]) continue;
flag=1;
vis[x]=1;
K[dep]--;
Colr(x);
Dfs(dep+1,Sum+K[dep]);
vis[x]=0;
K[dep]++;
iColr(x);
}
if (!flag) Dfs(dep+1,Sum);
}
int main() {
n=read(); m=read();
if (n==1) {
puts("1");
return 0;
}
for (int i=1;i<=m;i++) {
int x=read(),y=read();
Add(x,y); Add(y,x);
}
ans=Big;
Bfs();
Dfs(2,1);
printf("%d",ans);
}
