图论DFS：黑红树
https://i-blog.csdnimg.cn/blog_migrate/53d454b46f0e4ed423fbc59aa79ba6e1.png#pic_center
我的个人主页 {\large \mathsf{{\color{Red} 我的个人主页} } } 我的个人主页
往 {\color{Red} {\Huge 往} } 往 期 {\color{Green} {\Huge 期} } 期 文 {\color{Blue} {\Huge 文} } 文 章 {\color{Orange} {\Huge 章}} 章
[*]DFS 算法࿱
a;记忆化搜刮
[*]DFS 算法࿱
a;全排列题目
[*]DFS 算法࿱
a;洛谷B3625迷宫寻路
此系列更新频仍，求各位读者点赞
关注我可以相识更多内容哦
偷偷告诉你，我正在冲 1
1
00 粉 {\color{Gray} {\small 偷偷告诉你，我正在冲1
1
00粉} } 偷偷告诉你，我正在冲1
1
00粉
你们有什么想相识的可以发在批评区，我会仔细的看 {\color{Gray} {\small 你们有什么想相识的可以发在批评区，我会仔细的看} } 你们有什么想相识的可以发在批评区，我会仔细的看
1
1
00 粉时我会抓几个做文章 {\color{Gray} {\small1
1
00粉时我会抓几个做文章} } 1
1
00粉时我会抓几个做文章
今天我们学什么
今天我们不学什么，就是做一道图论DFS的题目
题目
题目描述
给定一棵树，每个结点有一个整数权值，一开始每个结点均为黑色。
若相邻两个黑色结点的权值之和为质数，我们就可以把其中的一个结点变成红色。问最多可以把多少个点变为红色。
输入格式
第一行一个整数 n n n，表现树的结点数量。
第二行 n n n 个整数 a 1
, ⋯ , a n a_1
, \cdots, a_n a1
,⋯,an，表现每个结点的权值。
接下来的 n − 1
n-1
n−1
行，每行两个整数 x , y x,y x,y，表现结点 x , y x,y x,y 之间有一条边。
输出格式
一个整数，表现最多可以把多少个点变为红色。
样例 #1
样例输入 #1
3
1
2 3
1
3
1
2
样例输出 #1
1
提示
测试点编号 n n n a i a_i ai1
,2 1
≤ n ≤ 20 1
\le n\le 20 1
≤n≤20 1
≤ a i ≤ 1
00 1
\le a_i\le 1
00 1
≤ai≤1
003,4 1
≤ n ≤ 1
000 1
\le n\le 1
000 1
≤n≤1
000 1
≤ a i ≤ 1
000 1
\le a_i\le 1
000 1
≤ai≤1
0005,6,7 1
≤ n ≤ 1
0 5 1
\le n\le 1
0^5 1
≤n≤1
05 1
≤ a i ≤ 1
0 5 1
\le a_i\le 1
0^5 1
≤ai≤1
058,9,1
0 1
≤ n ≤ 3 × 1
0 5 1
\le n\le 3\times 1
0^5 1
≤n≤3×1
05 1
≤ a i ≤ 1
0 6 1
\le a_i\le 1
0^6 1
≤ai≤1
06 题解
思绪
简单的图论DFS模板题目，稍稍修改模板即可
代码
#include <bits/stdc++.h>using namespace std;const int N=
;300005;vector<int> G;int value,ans,n;bool visited;bool is_prime;void dfs(int step){ int now=
;value; visited=
;true; for(auto a:G) { if(!visited) { int temp=
;value; if(is_prime) { ans++; } dfs(a); } }}int main(){ memset(is_prime,true,sizeof(is_prime)); is_prime=
;is_prime[1
]=
;false; for(int i=
;2; i<=
;2000000; i++) { if(is_prime) { for(int j=
;2; i*j<=
;2000000; j++) { is_prime=
;false; } } } cin>>n; for(int i=
;1
; i<=
;n; i++) { cin>>value; } for(int i=
;1
; i<n; i++) { int x,y; cin>>x>>y; G.push_back(y); G.push_back(x); } for(int i=
;1
; i<=
;n; i++) { if(!visited) { dfs(i); } } cout<<ans; return 0;} 怎么样，这是不是很简单呢࿱
f;
总结
有一些题是模板题，此时套上模板稍稍修改即可
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao1
23.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]