荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: gybeango (Heymo), 信区: Program
标  题: 一个有趣的题~!
发信站: 荔园晨风BBS站 (Sun Apr  6 13:06:49 2003), 站内信件

题目描述:

有一个国家被一条何划分为南北两部分,在南岸和北岸总共有N个城镇,每一城镇
在对岸都
有唯一的友好城镇。任何两个城镇都
没有相同的友好城镇。每一对友好城镇都希望有一条航线来往。于是他们向政府提
出了申请
。由于河终年有雾。政府决定不允许
有任两条航线交叉(如果两条航线交叉,将有很大机会撞船)。
你的任务是缟写一个程序来帮政府官员决定他们应拨款兴建哪些航线以使到没有出
现交叉的
航线最多。

题目输入:

输入包括了若干组数据,每组数据格式如下:
第一行两个由空格分隔的整数x,y,10〈=x〈=6000,10〈=y〈=100。x 表示河的
长度而y表
示宽。第二行是一个整数N(1<=N<=5000),
表示分布在河两岸的城镇对数。接下来的N行每行有两个由空格分隔的正数C,D(
C、D〈=x
〉,描述每一对友好城镇沿着河岸与西边境线
的距离,C表示北岸城镇的距离而D表示南岸城镇的距离。在河的同一边,任何两个
城镇的位
置都是不同的。


题目输出:

输出文件要在连续的若干行里给出每一组数据在安全条件下能够开通的最大航线数
目。

测试数据:

(输入)
30 4
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
(输出)

4

测试数据:

(输入)
30 4
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
(输出)

4

--

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.1.61]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店