pascal问题询问
来源:百度知道 编辑:UC知道 时间:2024/06/13 22:17:56
【联赛练习题目】连接格点
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 98 通过数: 27
【题目描述】
有一个M行N列的点阵,相邻两点可以相连。一条纵向的连线花费一个单位,一条横向的连线花费两个单位。某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。
【输入】
第一行输入两个正整数m和n。
以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1-x2|+|y1-y2|=1。
【输出】
输出使得连通所有点还需要的最小花费。
【输入样例】
2 2
1 1 2 1
【输出样例】
3
【提示】
数据规模:
m,n<=1000
这样一个题目 阐述方法 以及 程序
当然 我会追加分的
支持留QQ在线教学 拜师也可以~····~~~
如果是按照一楼说的 那每一个上下两个点都需要连接的么?
谁能给个程序 pascal的
最好能来个师傅!
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 98 通过数: 27
【题目描述】
有一个M行N列的点阵,相邻两点可以相连。一条纵向的连线花费一个单位,一条横向的连线花费两个单位。某些点之间已经有连线了,试问至少还需要花费多少个单位才能使所有的点全部连通。
【输入】
第一行输入两个正整数m和n。
以下若干行每行四个正整数x1,y1,x2,y2,表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1-x2|+|y1-y2|=1。
【输出】
输出使得连通所有点还需要的最小花费。
【输入样例】
2 2
1 1 2 1
【输出样例】
3
【提示】
数据规模:
m,n<=1000
这样一个题目 阐述方法 以及 程序
当然 我会追加分的
支持留QQ在线教学 拜师也可以~····~~~
如果是按照一楼说的 那每一个上下两个点都需要连接的么?
谁能给个程序 pascal的
最好能来个师傅!
就是特殊图的最小生成树。
先枚举每一条竖线,假若两个格点i,j没有连通就将其连上
然后同样的方法枚举每一条横线,就可以了
具体实现的时候可以使用并查集
程序我有,不过是C++的
还是自己写好一点
思路总有了吧!
图的最小生成树
图的最小生成树