青少年软件编程（C语言）等级考试试卷（九级）
1
图像分割
图像分割实际上是图的连通分量划分问题。将每个像素看成图中的一个顶点，顶点之间的边有权重，是相邻两个像素之间的区分度（非负整数）。图像分割的目标就是将图像构成的图分割成若干个不相交的连通分量，使得同一个分量中的像素都相似，而不同分量中的像素不相似。
连通分量的定义如下：
- 连通分量是一个互相连通的顶点的集合；
- 任何两个连通分量之间没有共同的顶点；
- 任何两个连通分量 C
1
和 C
2
之间的区分度 D(C
1
,C
2
) 大于这两个连通分量的内聚度 H；
- 区分度 D(C
1
,C
2
) 定义为连接 C
1
和 C
2
的所有边权重中的最小值，如果不存在连接边，则这个值定义为无穷大；
- 连通分量 C 的内聚度 H(C) 定义为 C 的最小生成树中的最大边权重，外加一个函数值 f(C)=c/|C|，其中 c 是一个正整数常量，|C| 是 C 的规模，即顶点个数；
- 如果一个顶点集合还能被划分为两个及以上的连通分量，则这个集合不能算做是一个连通分量。
你的任务就是列出所有连通分量。
时间限制：1000
内存限制：65536
输入
第一行输入三个整数：N
v
（1 < N
v
≤ 1000）为顶点数量（顶点从 0 到 N
v
-1 编号）；N
e
为边的数量；c 是函数 f(C) 中的那个常数。随后 N
e
行，每行按以下格式给出一条边： 顶点1编号 顶点2编号 权重 注意：题目保证每个像素点有不超过 8 个相邻的像素点。常数和所有的权重均不超过 1000。
输出
每行输出一个连通分量。每个连通分量的顶点要在一行中按编号升序输出，数字间以 1 个空格分隔，行首尾不得有多余空格。连通分量按照其首个顶点的升序输出。
样例输入
样例#1：
10 21 100
0 1 10
0 3 60
0 4 90
1 2 90
1 3 50
1 4 200
1 5 86
2 4 95
2 5 5
3 4 95
3 6 15
3 7 101
4 5 500
4 6 100
4 7 101
4 8 101
5 7 300
5 8 50
6 7 90
7 8 84
7 9 34
样例#2：
7 7 100
0 1 10
1 2 61
2 3 50
3 4 200
4 5 82
5 0 200
3 6 90
样例输出
样例#1：
0 1 3 6
2 5 8
4
7 9
样例#2：
0 1
2 3 6
4 5
2
迎风一刀斩
迎着一面矩形的大旗一刀斩下，如果你的刀够快的话，这笔直一刀可以切出两块多边形的残片。反过来说，如果有人拿着两块残片来吹牛，说这是自己迎风一刀斩落的，你能检查一下这是不是真的吗？
注意摆在你面前的两个多边形可不一定是端端正正摆好的，它们可能被平移、被旋转（逆时针90度、180度、或270度），或者被（镜像）翻面。
这里假设原始大旗的四边都与坐标轴是平行的。
202503C语言九级