周口市网站建设,开发一个oa系统多少钱,杭州做官网的有哪些公司,重庆建设工程信息网官网入渝备案题目
题目背景
本题是错题#xff0c;后来被证明没有靠谱的多项式复杂度的做法。测试数据非常的水#xff0c;各种玄学-做法都可以通过#xff0c;不代表算法正确。因此本题题目和数据仅供参考。 近来#xff0c;一种新的传染病肆虐全球。蓬莱国也发现了零星感染者#…题目
题目背景
本题是错题后来被证明没有靠谱的多项式复杂度的做法。测试数据非常的水各种玄学-做法都可以通过不代表算法正确。因此本题题目和数据仅供参考。 近来一种新的传染病肆虐全球。蓬莱国也发现了零星感染者为防止该病在蓬莱国大范围流行该国政府决定不惜一切代价控制传染病的蔓延。不幸的是由于人们尚未完全认识这种传染病难以准确判别病毒携带者更没有研制出疫苗以保护易感人群。于是蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO世界卫生组织以及全球各国科研部门的努力这种新兴传染病的传播途径和控制方法已经研究清楚剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。
题目描述
研究表明这种传染病的传播具有两种很特殊的性质 第一是它的传播途径是树型的一个人X只可能被某个特定的人Y感染只要Y不得病或者是XY之间的传播途径被切断则X就不会得病。 第二是这种疾病的传播有周期性在一个疾病传播周期之内传染病将只会感染一代患者而不会再传播给下一代。 这些性质大大减轻了蓬莱国疾病防控的压力并且他们已经得到了国内部分易感人群的潜在传播途径图一棵树。但是麻烦还没有结束。由于蓬莱国疾控中心人手不够同时也缺乏强大的技术以致他们在一个疾病传播周期内只能设法切断一条传播途径而没有被控制的传播途径就会引起更多的易感人群被感染也就是与当前已经被感染的人有传播途径相连且连接途径没有被切断的人群。当不可能有健康人被感染时疾病就中止传播。所以蓬莱国疾控中心要制定出一个切断传播途径的顺序以使尽量少的人被感染。 你的程序要针对给定的树找出合适的切断顺序。
输入格式
第一行是两个整数n和p。 接下来p行每一行有2个整数i和j表示节点i和j间有边相连。意即第i人和第j人之间有传播途径相连。其中节点1是已经被感染的患者。
输出格式
1行总共被感染的人数
样例
输入
7 6
1 2
1 3
2 4
2 5
3 6
3 7输出
3说明/提示
对于 100 % 100\% 100%的数据, 1 ≤ n ≤ 300 1 \leq n \leq 300 1≤n≤300。
思路
不出意外的话这题绝对是dfs 再根据题意这肯定是个树 这题的重点就在于将一棵无根的无根感染树转化成以1为根的有根感染树 具体知识详见刘汝佳的《算法竞赛入门经典》
代码
#includebits/stdc.h
using namespace std;
const int maxn305;
int n,p;
vectorint G[maxn],vertex[maxn];//邻接表同一层的结点
int tot[maxn];
int fa[maxn],sz[maxn],ans130;//每个节点的父节点后缀
bool infected[maxn];//是否被感染
void dfs(int i,int d){//无根-有根 vertex[d].push_back(i);sz[i]1;for(int j:G[i]){if(jfa[i]) continue;fa[j]i,dfs(j,d1),sz[i]sz[j];}
}
void work(int i,int sum){//真dfsif(anssum) return;//最优性剪枝bool have0;for(int j:vertex[i]) if(infected[fa[j]]) infected[j]1,sum,have1;//假设都感染了if(!have) { ansmin(ans,sum);return; }//如果都感染了就直接更新答案for(int j:vertex[i]) if(infected[fa[j]]) infected[j]0,work(i1,sum-1),infected[j]1;for(int j:vertex[i]) if(infected[fa[j]]) infected[j]0;//回溯
}
int main()
{cinnp;for(int i1,x,y;ip;i) cinxy,G[x].push_back(y),G[y].push_back(x);//不确定指向所以存双向边dfs(1,0),infected[1]1,work(1,1);coutans;return 0;
}相信读者此时已经将代码理解透彻笔者不再做赘述
end
完结撒花
