为什么要建设旅游网站,东莞房价下跌最惨一览表,ss永久免费服务器,做们作业网站时间限制:2000ms单点时限:1000ms内存限制:256MB描述 给定2个树A和B#xff0c;保证A的节点个数B的节点个数。 现在你需要对树A的边进行二染色。 一个好的染色方案#xff0c;指不存在一个树A中的连通块#xff0c;同时满足以下2个条件 1. 其中只有同色的边 2. 和B同构。… 时间限制:2000ms 单点时限:1000ms 内存限制:256MB 描述 给定2个树A和B保证A的节点个数B的节点个数。 现在你需要对树A的边进行二染色。 一个好的染色方案指不存在一个树A中的连通块同时满足以下2个条件 1. 其中只有同色的边 2. 和B同构。两个树同构是指存在一个一一映射既是单射又是满射将树B的各节点映射到不同的树A的节点使得原来在树B中相邻的点在映射后仍相邻。 问是否存在一种好的染色方案。 输入 第一行一个整数T (1T10)表示数据组数。 接下来是T组输入数据测试数据之间没有空行。 每组数据格式如下 第一行一个整数N 表示树A的节点总数。 接下来N-1行每行2个数a, b (1 a, b N)表示树A的节点a和b之间有一条边。 接下来一行一个整数M(1 M N)表示树B的节点总数。 接下来M-1行每行2个数a, b (1 a, b M)表示树B的节点a和b之间有一条边。 输出 对每组数据先输出“Case x: ”x表示是第几组数据然后接“YES”/“NO”表示是否存在所求的染色方案。 数据范围 小数据1 N 20 大数据1 N 1000000 样例解释 无论如何染色只要从A中挑一条边就行了。 样例输入 1
3
1 2
2 3
2
1 2样例输出 Case 1: NO 题目解析 1. 两棵树 A B node(A) node(B) 对 A 二染色与 B 同构部分不能只有一种颜色。 2.问题转化为对 A 二染色颜色相同的部分不能与 B 同构。 3. 举例 A ———————————— B’ 由 A 得出最大边同色树 其中A 的根结点的度最大为 5 则它连接的边必定有 3 条相同无论如何染色。而那些与根节点不相关的边可以任意染色。 若 B 是 B’ 的子树则答案是 NO否则答案是 YES。 由此图得出样例输入 输出 1 12 1 2 1 3 …… 5 12 4 1 2 1 3 1 4 Case 1: NO 4解题思路在树 A 中找出度最大设为 D的节点进而求出树 B’ 1个根节点(D1)/2 个叶节点深度为 1 判断 B 是否是 B’ 的子树若是则 NO否 则 YES。 code: 1 #includestdio.h2 #includememory.h3 const int MAX 1e6 1;4 int d1[MAX];5 int d2[MAX];6 int main(){7 int T, M, N;8 scanf(%d,T);9 for(int k 0; k T; k){
10 memset(d1, 0, sizeof(d1));
11 memset(d2, 0, sizeof(d2));
12 int v1, v2;
13 scanf(%d, N);
14 for(int i 1; i N; i){
15 scanf(%d%d, v1, v2);
16 d1[v1]; d1[v2];
17 }
18 scanf(%d, M);
19 for(int i 1; i M; i){
20 scanf(%d%d, v1, v2);
21 d2[v1]; d2[v2];
22 }
23 int D 0, Mleaf 0;
24 for(int i 1; i N; i){
25 if(d1[i] D) D d1[i];
26 if(d2[i] 1) Mleaf;
27 }
28 if(M 3) --Mleaf; // remove root Node
29 if(Mleaf M - 1 Mleaf (D 1) / 2)
30 printf(Case %d: NO\n, k1);
31 else printf(Case %d: YES\n, k1);
32 }
33 return 0;
34 } 转载于:https://www.cnblogs.com/liyangguang1988/p/3664434.html
