| 题目名称 | 1918. [SHOI 2008] 仙人掌图 |
|---|---|
| 输入输出 | bzoj_1023.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Asm.Def
于2015-03-22加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：42， 提交：142， 通过率：29.58% | ||||
 gryzy |
100 | 0.020 s | 8.79 MiB | C++ |
 Shirry |
100 | 0.024 s | 4.09 MiB | C++ |
|
gryzy |
100 | 0.025 s | 6.58 MiB | C++ |
 神利·代目 |
100 | 0.026 s | 32.07 MiB | C++ |
 yuan |
100 | 0.027 s | 3.01 MiB | C++ |
 Twilight_ |
100 | 0.030 s | 26.05 MiB | C++ |
 XLightGod |
100 | 0.045 s | 6.80 MiB | C++ |
 niconicoqaq |
100 | 0.045 s | 79.09 MiB | C++ |
 Steven |
100 | 0.046 s | 3.17 MiB | C++ |
|
Steven |
100 | 0.048 s | 3.17 MiB | C++ |
| 关于 仙人掌图 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
我可能开了假的O2
数据过水，差评 | ||||
|
卧槽。。。。。。
0.000s，我是不是开挂了。。。。。。 | ||||
|
仙人掌的性质好优美啊>_<
我太弱了只好去寻求晨耀的帮助……Orzzzzzzz @Chenyao2333 顺便……给这种题造数据实在不好玩……最后的“数据按路径给出”我实在不会…于是就去掉了原题中对路径数和路径上点数的限制= = | ||||
如果某个无向连通图的任意一条边至多只出现在一条简单回路（simple cycle）里，我们就称这张图为仙人图（cactus）。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。
举例来说，上面的第一个例子是一张仙人图，而第二个不是——注意到它有三条简单回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，2，1，6，5，4），而（2，3）同时出现在前两个的简单回路里。另外，第三张图也不是仙人图，因为它并不是连通图。显然，仙人图上的每条边，或者是这张仙人图的桥（bridge），或者在且仅在一个简单回路里，两者必居其一。定义在图上两点之间的距离为这两点之间最短路径的距离。定义一个图的直径为这张图相距最远的两个点的距离。现在我们假定仙人图的每条边的权值都是1，你的任务是求出给定的仙人图的直径。
输入的第一行包括两个整数n和m（1≤n≤50000）。其中n代表顶点个数，我们约定图中的顶点将从1到n编号。接下来一共有m行。代表m条路径。每行的开始有一个整数k，代表在这条路径上的顶点个数。接下来是k个1到n之间的整数，分别对应了一个顶点，相邻的顶点表示存在一条连接这两个顶点的边。一条路径上可能通过一个顶点好几次，比如对于第一个样例，第一条路径从3经过8，又从8返回到了3，但是我们保证所有的边都会出现在某条路径上，而且不会重复出现在两条路径上，或者在一条路径上出现两次。
只需输出一个数，这个数表示仙人图的直径长度。
15 3 9 1 2 3 4 5 6 7 8 3 7 2 9 10 11 12 13 10 5 2 14 9 15 10
8
10 1 10 1 2 3 4 5 6 7 8 9 10
9
对第一个样例的说明：如图，6号点和12号点的最短路径长度为8，所以这张图的直径为8。
【注意】使用Pascal语言的选手请注意：你的程序在处理大数据的时候可能会出现栈溢出。如果需要调整栈空间的大小，可以在程序的开头填加一句：{$M 5000000}，其中5000000即指代栈空间的大小，请根据自己的程序选择适当的数值。
Asm.Def