hdu 5423 Rikka with Tree(dfs)bestcoder #53 div2 1002

时间:2021-07-27 00:17:14

题意:

输入一棵树,判断这棵树在以节点1为根节点时,是否是一棵特殊的树。

相关定义:

1.  定义f[A, i]为树A上节点i到节点1的距离,父节点与子节点之间的距离为1。

2.  对于树A与树B,如果A与B的节点数相同,且无论i为何值,f[A, i]与f[B, i]都相等,则A与B为两棵相似的树。

3.  对于一棵树A,在以节点1为根节点的情况下,如果不存在与其它树与A相似,则A是一棵特殊的树。

输入:

包含多组输入样例。

每组输入样例中首先输入一个整数n,表示一棵含有n个节点的树。

接下来n-1行,每行两个整数a, b表示a与b相连。

输出:

如果这棵树是特殊的树,输出YES,否则输出NO。每组样例占1行。

题解:

如果某个节点x的父节点fx到根节点fg的距离dis[fx]与另一个节点fy的dis[fy]相等,且fx != fy, 那么x在fy上的树与x在fx上的树是相似的。

  首先,我们可以证明,如果树A是一条以节点1为根的单链,那么这棵树是特殊的。

  其次,我们可以证明,如果树A以节点1为根时,除了叶节点的父节点出度为x(x>1)外,其它非子节点的出度都为1。那么这棵树也是特殊的。(当然上一个证明包含在这个证明中)。

  除此之外的所有情况,都是非特殊的。

因此,我们可以先计算出所有节点到根节点(节点1)的距离,然后分析得x2,x3,…xi,…,xn,xi即,到节点1的距离为i的点的数量。根据上面的结论,如果x2到xi的值为1,xi+1的值为m(1<=m<=n-1)则,这棵树是特殊的,否则不是。

计算树上任一点到节点1的距离,可以用dfs很方便得计算出来,但是在比赛的时候,我脑子抽了,居然用了最短路算法……当然,用最短路确实也能解。

其次,在统计结果的时候,我用的方法是将dis[],即节点到根节点的距离按从小到大排序,然后从前往后数,当dis[i] == dis[i+1] && dis[i+1] < dis[i+2]时,则不是特殊树。

看了别人的方法,是统计每种距离的数量的。

但是,我想说的一点是,我在用sort排序时,写的sort(dis+1, dis+n+1, cmp),其中的cmp(int x, int y)中由于直接写了个return x <= y; 所以爆re爆得欲仙欲死,显示非法访问内存了。然后将<=改成<,就过了……

用最短路算法时,3次Dijkstra,tle 1次,900+ms 2次。2次Spfa,都是700ms+。

用dfs,2次是排序的方法,分别是46ms,62ms,1次统计各距离,15ms……看来还是别人家的方法好T_T。

 #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int NN = ;
const int N = ; int mp[NN][NN];
int dis[NN];
bool vis[NN];
int n; bool cmp(int x, int y)
{
return x <= y; //就死在这个<=上了 = =
} void dij()
{
memset(vis, , sizeof(vis));
dis[] = ;
for(int i = ; i <= n; i++) dis[i] = mp[][i];
vis[] = ;
for(int i = ; i < n; i++)
{
int minn = N, k;
for(int j = ; j <= n; j++)
{
if(!vis[j] && minn > dis[j])
{
minn = dis[j];
k = j;
}
}
if(minn == N) break; vis[k] = ;
for(int j = ; j <= n; j++)
{
if(!vis[j] && dis[j] > dis[k]+mp[j][k]) dis[j] = dis[k]+mp[j][k];
}
}
} int main()
{
//freopen("test.in", "r", stdin);
while(~scanf("%d", &n))
{
for(int i = ; i <= n; i++)
{
for(int j = ; j < i; j++) mp[i][j] = mp[j][i] = N;
mp[i][i] = ;
} for(int i = ; i < n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
mp[a][b] = mp[b][a] = ;
}
dij();
sort(dis+, dis+n+, cmp);
bool flag = ; for(int i = ; i <= n-; i++)
{
if(dis[i] == dis[i+] && dis[i+] < dis[i+]) {flag = ; break;}
}
if(flag) printf("NO\n");
else printf("YES\n");
}
return ;
}

RE code

 #include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int NN = ;
const int N = ; int mp[NN][NN];
int dis[NN];
bool vis[NN];
int n; bool cmp(int x, int y)
{
return x < y; //...............
} void dij()
{
dis[] = ;
for(int i = ; i <= n; i++) dis[i] = mp[][i];
vis[] = ;
for(int i = ; i < n; i++)
{
int minn = N, k;
for(int j = ; j <= n; j++)
{
if(!vis[j] && minn > dis[j])
{
minn = dis[j];
k = j;
}
}
if(minn == N) break;
vis[k] = ;
for(int j = ; j <= n; j++)
{
if(!vis[j] && dis[j] > dis[k]+mp[j][k]) dis[j] = dis[k]+mp[j][k];
}
}
} void Spfa()
{
dis[] = ;
for(int i = ; i <= n; i++) dis[i] = N;
vis[] = ;
queue<int>que;
que.push(); int p;
while(!que.empty())
{
p = que.front();
que.pop();
vis[p] = ;
for(int i = ; i <= n; i++)
{
if(dis[i] > dis[p]+mp[i][p])
{
dis[i] = dis[p]+mp[i][p];
if(vis[i] == )
{
que.push(i);
vis[i] = ;
}
}
}
}
} int main()
{
//freopen("test.in", "r", stdin);
while(~scanf("%d", &n))
{
for(int i = ; i <= n; i++)
{
for(int j = ; j < i; j++) mp[i][j] = mp[j][i] = N;
mp[i][i] = ;
vis[i] = ;
} for(int i = ; i < n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
mp[a][b] = mp[b][a] = ;
}
//Spfa();
dij();
sort(dis, dis+n+, cmp);
bool flag = ; for(int i = ; i <= n-; i++)
{
if(dis[i] == dis[i+] && dis[i+] < dis[i+]) {flag = ; break;}
}
if(flag) printf("NO\n");
else printf("YES\n");
}
return ;
}

AC dij+spfa

 #include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std; const int N = ; struct Edge
{
int to, next;
}edge[N]; int dis[N], head[N];
bool vis[N];
int n; bool cmp(int x, int y)
{
return x < y;
} void add(int a, int b, int k)
{
edge[k].to = b;
edge[k].next = head[a];
head[a] = k;
} void init()
{
memset(edge, -, sizeof(edge));
memset(head, -, sizeof(head));
memset(dis, -, sizeof(dis));
for(int i = ; i < n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b, i);
}
} void dfs(int x, int k)
{
for(int i = head[x]; i != -; i = edge[i].next)
{
int v = edge[i].to;
if(!vis[v])
{
vis[v] = ;
dis[v] = k;
dfs(v, k+);
vis[v] = ;
}
}
} void outit()
{
/*
sort(dis, dis+n+1, cmp);
bool flag = 0;
for(int i = 2; i <= n-2; i++)
{
if(dis[i] == dis[i+1] && dis[i+1] < dis[i+2]) {flag = 1; break;}
}
if(flag) printf("NO\n");
else printf("YES\n");
*/
int sum[N];
memset(sum, , sizeof(sum));
for(int i = ; i <= n; i++) sum[dis[i]]++;
int ans = ;
for(int i = ; i <= n; i++)
{
if(sum[i] == ) ans++;
else
{
if(sum[i+] == ) ans = n;
break;
}
}
if(ans == n) printf("YES\n");
else printf("NO\n");
} int main()
{
//freopen("test.in", "r", stdin);
while(~scanf("%d", &n))
{
init();
dfs(, );
outit();
}
return ;
}

AC dfs

革命尚未成功,同志仍需努力

hdu 5423 Rikka with Tree(dfs)bestcoder #53 div2 1002的更多相关文章

  1. hdu 5423 Rikka with Tree(dfs)

    Problem Description As we know, Rikka is poor at math. Yuta is worrying about this situation, so he ...

  2. (hdu)5423 Rikka with Tree (dfs)

    题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=5423 Problem Description As we know, Rikka is p ...

  3. HUD5423 Rikka with Tree(DFS)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5423 Rikka with Tree Time Limit: 2000/1000 MS (Java/O ...

  4. HDU 2553 N皇后问题(dfs)

    N皇后问题 Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Description 在 ...

  5. 2017ACM暑期多校联合训练 - Team 1 1003 HDU 6035 Colorful Tree (dfs)

    题目链接 Problem Description There is a tree with n nodes, each of which has a type of color represented ...

  6. HDU 5423&colon;Rikka with Tree Dijkstra算法

    Rikka with Tree  Accepts: 207  Submissions: 815  Time Limit: 2000/1000 MS (Java/Others)  Memory Limi ...

  7. HDU 5416 CRB and Tree (技巧)

    题意:给一棵n个节点的树(无向边),有q个询问,每个询问有一个值s,问有多少点对(u,v)的xor和为s? 注意:(u,v)和(v,u)只算一次.而且u=v也是合法的. 思路:任意点对之间的路径肯定经 ...

  8. ACM学习历程—HDU5423 Rikka with Tree(搜索)

    Problem Description As we know, Rikka is poor at math. Yuta is worrying about this situation, so he ...

  9. hdu 1016 Prime Ring Problem(dfs)

    Prime Ring Problem Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Other ...

随机推荐

  1. sublime jsx 格式化工具

    1.到Sublime Text 3\Packages\ 目录下 git clone https://github.com/ionutvmi/sublime-jsfmt jsfmt 2.重启sublim ...

  2. javase基础复习攻略《二》

    今天就开始的真正走进JAVASE的世界,本篇介绍的是:JAVASE基础语法,大家如果有C语言的基础,对于本节内容一定感觉非常轻松,编程语言之间的都是相通的,只不过C语言属于面向过程编程,而JAVA语言 ...

  3. 对于C&plus;&plus;窗口编译一闪而过的解决方法 (DEV CPP下)

    对于C++窗口编译一闪而过的解决方法 首先来看一个简单的程序(编译环境为 DEV C++.):  #include <iostream>  int main()  {      std:: ...

  4. Java 中的反射机制

    JAVA反射机制 JAVA反射机制是在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法:对于任意一个对象,都能够调用它的任意一个方法:这种动态获取的信息以及动态调用对象的方法的功能称为ja ...

  5. rabbitmq学习笔记2 基本概念

    官网:http://www.rabbitmq.com 参考:http://blog.csdn.net/column/details/rabbitmq.html   1 基本概念 rabbitmq se ...

  6. 搭建docker私有仓库,建立k8s集群

    服务器IP角色分布 192.168.5.2 etcd server 192.168.5.2 kubernetes master 192.168.5.3 kubernetes node 192.168. ...

  7. python中归并排序

    # coding=UTF-8 #!/usr/bin/python import sys def merge(nums, first, middle, last): "merge" ...

  8. 201521123008《Java程序设计》第六周实验总结

    1.本周学习总结 2.书面作业 1.clone方法 1.1 Object对象中的clone方法是被protected修饰,在自定义的类中覆盖clone方法时需要注意什么? 因为被protected修饰 ...

  9. 关于Mybatis的java&period;lang&period;UnsupportedOperationException异常处理

    圈住的那行报java.lang.UnsupportedOperationException这个错,这个错的意思是:不支持的操作异常 异常我就不贴了,直接上解决办法吧. 可能我的异常跟大家的不太一样,报 ...

  10. 使用UE4&sol;Unity创建VR项目

    一.主要的步骤是说一下使用UE4,在此之前先说一下使用unity创建的VR项目 1.unity创建oculus rift dk2项目 在unity中创建一个简单的场景,让摄像机能看见场景中的物体,不对 ...