题解 P1041 【传染病控制】
顾z
2018-07-25 20:49:36
贪心虽然被卡成了90分 ~~但我还是决定放我丑陋的代码~~
思想：每层选择子树最大的节点,
并去标记一下他的后辈们,
然后再搜到下一层,我们就继续的去选取
子树最大的节点。
如此往复
我们拆下来的就是最多的,用n减去我们的ans即可
然后 感谢@All_will的点拨.
献上优(chou)美(lou)的代码：
```cpp
#include<bits/stdc++.h>
#define IL inline
#define RI register int
int n,p,u,v;
struct code{
int u,v;
}edge[8888];int lala;
int head[333],tot,depth[333],f[333],size[333],maxdepth,ans;
bool vis[333];
IL void dfs(int u,int fa)
{
depth[u]=depth[fa]+1;f[u]=fa;
maxdepth=std::max(maxdepth,depth[u]);
size[u] = 1;
for(RI i=head[u];i;i=edge[i].u)
{
if(edge[i].v==fa)continue;
dfs(edge[i].v,u);
size[u] += size[edge[i].v];
}
}
IL void add(int x,int y)
{
edge[++tot].u=head[x];
edge[tot].v=y;
head[x]=tot;
edge[++tot].u=head[y];
edge[tot].v=x;
head[y]=tot;
}
IL void gengxin(int x)
{
size[x]=0;
vis[x]=true;
for(RI i=head[x];i;i=edge[i].u)
{
if(edge[i].v==f[x])continue;
gengxin(edge[i].v);
}
}
IL void search(int dep)
{
int maxtree,mxx=0;
for(RI i=1;i<=n;i++)
{
if(!vis[i]&&depth[i]==dep)
{
if(size[i]>mxx)
{
mxx=size[i];
maxtree=i;
}
}
}
ans+=size[maxtree];
gengxin(maxtree);
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin>>n>>p;
for(RI i=1;i<=p;i++)
{
std::cin>>u>>v;
add(u,v);
}
dfs(1,0);
for(RI i=2;i<=maxdepth;i++)
search(i);
//for(int i = 1;i <= n;++i)printf("vis[%d] = %d\n",i,vis[i]);
std::cout<< n - ans;
}
```
待我研究搜索再来get此题 emmm