NOIP2003传染病控制[按层DFS]

时间:2022-12-17 16:28:44

题目背景

近来,一种新的传染病肆虐全球。蓬莱国也发现了零星感染者,为防止该病在蓬莱国大范围流行,该国*决定不惜一切代价控制传染病的蔓延。不幸的是,由于人们尚未完全认识这种传染病,难以准确判别病毒携带者,更没有研制出疫苗以保护易感人群。于是,蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO(世界卫生组织)以及全球各国科研部门的努力,这种新兴传染病的传播途径和控制方法已经研究清楚,剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。

题目描述

研究表明,这种传染病的传播具有两种很特殊的性质;

第一是它的传播途径是树型的,一个人X只可能被某个特定的人Y感染,只要Y不得病,或者是XY之间的传播途径被切断,则X就不会得病。

第二是,这种疾病的传播有周期性,在一个疾病传播周期之内,传染病将只会感染一代患者,而不会再传播给下一代。

这些性质大大减轻了蓬莱国疾病防控的压力,并且他们已经得到了国内部分易感人群的潜在传播途径图(一棵树)。但是,麻烦还没有结束。由于蓬莱国疾控中心人手不够,同时也缺乏强大的技术,以致他们在一个疾病传播周期内,只能设法切断一条传播途径,而没有被控制的传播途径就会引起更多的易感人群被感染(也就是与当前已经被感染的人有传播途径相连,且连接途径没有被切断的人群)。当不可能有健康人被感染时,疾病就中止传播。所以,蓬莱国疾控中心要制定出一个切断传播途径的顺序,以使尽量少的人被感染。

你的程序要针对给定的树,找出合适的切断顺序。

输入输出格式

输入格式:

输入格式的第一行是两个整数n(1≤n≤300)和p。接下来p行,每一行有两个整数i和j,表示节点i和j间有边相连(意即,第i人和第j人之间有传播途径相连)。其中节点1是已经被感染的患者。

输出格式:

只有一行,输出总共被感染的人数。

输入输出样例

输入样例#1:
7 6
1 2
1 3
2 4
2 5
3 6
3 7
输出样例#1:

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
贪心不行,很明显树上DFS
然后不想想随手打了个每个节点都可以cut掉一个孩子的DFS,结果发现是每一个deep可以cut一个孩子
这样DFS节点反而不方便,不如按深度(一层一层)DFS
维护当前深度d和当前感染人数sum
所有深度是d的人,先通过fa来处理会不会感染,更新sum;
然后枚举cut掉当前深度的一个人,别忘sum--,dfs下一层
sum>ans剪枝,当前deep没人更新答案
建树时可以把同一深度组织在一起,会很快
注意一开始cut[1]=0,其他全1
//
// main.cpp
// noip2003ill
//
// Created by abc on 16/8/16.
// Copyright ? 2016年 abc. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=,M=;
struct edge{
int v,ne;
}e[M];
int h[N],cnt=;
int n,p;
int ans=1e5;
inline void ins(int x,int y){
cnt++;
e[cnt].v=y;e[cnt].ne=h[x];h[x]=cnt;
cnt++;
e[cnt].v=x;e[cnt].ne=h[y];h[y]=cnt;
}
int fa[N],deep[N],dl[N][N];
void build(int u){
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(v==fa[u]) continue;
deep[v]=deep[u]+;
dl[deep[v]][++dl[deep[v]][]]=v;
fa[v]=u;
build(v);
}
}
int cut[N];
void dfs(int d,int sum){//printf("dfs %d\n",d);
if(sum>=ans) return;
int flag=;
for(int i=;i<=dl[d][];i++){
int u=dl[d][i]; //printf("u %d\n",u);
if(cut[fa[u]]==) {cut[u]=;sum++;flag=;}
}
if(flag) sum--;//cut one of d
for(int i=;i<=dl[d][];i++){
int u=dl[d][i]; //printf("cut %d\n",u);
if(cut[u]) continue;
cut[u]=;
dfs(d+,sum);
cut[u]=;
}
for(int i=;i<=dl[d][];i++){
int u=dl[d][i]; //printf("u %d\n",u);
cut[u]=;
} if(flag==) ans=min(ans,sum);//printf("sum %d %d\n",d,sum);
}
int main(int argc, const char * argv[]) {
scanf("%d%d",&n,&p);//cout<<"\n\np "<<p<<"\n\n";
for(int i=;i<=p;i++){
int x,y;
scanf("%d%d",&x,&y);
ins(x,y);
//printf("i %d %d %d\n",i,x,y);
}
build();
for(int i=;i<=n;i++) cut[i]=;cut[]=;
dfs(,);//root-0 is already
cout<<ans;
return ;
}


NOIP2003传染病控制[按层DFS]的更多相关文章

  1. &lbrack;NOIP2003&rsqb; 传染病控制题解

    问题 F: [NOIP2003] 传染病控制 时间限制: 1 Sec  内存限制: 128 MB 题目描述 [问题背景] 近来,一种新的传染病肆虐全球.蓬莱国也发现了零星感染者,为防止该病在蓬莱国大范 ...

  2. 【NOIP2003】传染病控制(-贪心&sol;dfs)

    我自己yy了个贪心算法,在某oj 0msAC~.然后去wikioi提交,呵呵,原来是之前oj的数据太弱给我水过了,我晕. 我之前的想法是在这棵树上维护sum,然后按时间来割边,每一时刻割已经感染的人所 ...

  3. NOIP2003 传染病控制

    题四     传染病控制 [问题背景] 近来,一种新的传染病肆虐全球.蓬莱国也发现了零星感染者,为防止该病在蓬莱国 大范围流行,该国*决定不惜一切代价控制传染病的蔓延.不幸的是,由于人们尚未完 全认 ...

  4. NOIP2003 传染病控制 【搜索 &plus; 卡时】

    题目背景 近来,一种新的传染病肆虐全球.蓬莱国也发现了零星感染者,为防止该病在蓬莱国大范围流行,该国*决定不惜一切代价控制传染病的蔓延.不幸的是,由于人们尚未完全认识这种传染病,难以准确判别病毒携带 ...

  5. Luogu1041 NOIP2003传染病控制(搜索)

    暴搜加个最优性剪枝即可.一直觉得正式比赛出这种不能一眼看出来暴搜就行了的搜索题的出题人都是毒瘤. #include<iostream> #include<cstdio> #in ...

  6. &lbrack;NOIP2003&rsqb; 传染病控制 搜索&plus;剪枝

    搜索的最广泛应用优化——剪枝 这道题的dp和贪心都是无正确性的,所以,搜~~~~~~~ 搜的时候你发现不剪枝极容易被卡掉(然而良心NOIP没有这么做,不剪枝仍然飞快),所以我们需要一些玄学的剪枝最常见 ...

  7. &lbrack;COGS 0107&rsqb;&lbrack;NOIP 2003&rsqb; 传染病控制

    107. [NOIP2003] 传染病控制 ★★★   输入文件:epidemic.in   输出文件:epidemic.out   简单对比时间限制:1 s   内存限制:128 MB [问题背景] ...

  8. hdu 4403 dfs

    巨麻烦的模拟题orz.... 先确定等号的位置,然后两层dfs,分别算等号前面的和后面的,再比较 话说这题竟然不开long long都能水过 #include <iostream> #in ...

  9. Codeforces 383C &period; Propagating tree【树阵,dfs】

    标题效果: 有一棵树,有两种操作模式对本树:1:表示为(1 x val),在NOx加在节点上val,然后x每个节点加上儿子- val.给每个儿子一个儿子在一起-(- val),加到没有儿子为止.2:表 ...

随机推荐

  1. 苹果手机Safari无痕浏览模式下系统登录成功但是页面不跳转

    昨天下午,测试提了一个bug,问题是:在苹果手机Safari无痕浏览模式下系统登录成功但是页面不跳转. 思前想后找了半天没思路,后来经过同事的点拨,说可能是禁用了cookie之类的,反正我也没思路就顺 ...

  2. iscroll 加载不全解决方案

    例如上图中,get_kaijiang 中如果执行一段ajax跨域传输的话 function get_kaijiang(){ ajax------- $('#div').append(html); -- ...

  3. delayed ack与nagle&&num;39&semi;s算法

    delayed ack和nagles算法都能减少tcp传输过程中的小数据包的问题 tcpip卷二25章中提到tcp为每个连接建立7个定时器: 1.connection established 2.re ...

  4. sublime 配置C&plus;&plus;

    1. 安装C语言编译器MinGW,并把MinGW安装目录下的bin目录添加到环境变量PATH里.详细方法参照MinGW安装和使用 2. 在SublimeText安装目录下的Data\Packages\ ...

  5. Java Web编程的主要组件技术——Servlet

    参考书籍:<J2EE开源编程精要15讲> Servlet是可以处理客户端传来的HTTP请求,并返回响应,由服务器端调用执行,有一定编写规范的Java类. 例如: package test; ...

  6. mysql在高内存、IO利用率上的几个优化点 &lpar;sync&plus;fsync&rpar; 猎豹移动技术博客

    http://dev.cmcm.com/archives/107 Posted on 2014年10月16日 by liuding | 7条评论 以下优化都是基于CentOS系统下的一些优化整理,有不 ...

  7. JQ动画,背景透明度

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...

  8. android stuido 快捷键

    Alt+回车 导入包,自动修正 Ctrl+N   查找类 Ctrl+Shift+N 查找文件 Ctrl+Alt+L  格式化代码 Ctrl+Alt+O 优化导入的类和包 Alt+Insert 生成代码 ...

  9. django模板语法之include

    假如我们有以下模板index.html,代码为: <!DOCTYPE html> <html lang="en"> <head> <met ...

  10. JAVA入门&lbrack;14&rsqb;-Spring MVC AOP

    一.基本概念 1.AOP简介 DI能够让相互协作的软件组件保持松散耦合:而面向切面编程(aspect-oriented programming,AOP)允许你把遍布应用各处的功能分离出来形成可重用的组 ...