网站页面
当前课程
成员
常规
第一章 分治算法
第二章 递归算法
第三章 排列组合问题
第四章 高精度算法
第五章 排序算法
第六章 穷举算法
第七章 贪心算法
第八章 递推算法
第九章 搜索算法
第十章 模拟算法
友好城市
成绩 | 100 | 开启时间 | 2016年05月29日 星期日 17:40 |
折扣 | 0.8 | 折扣时间 | 2016年05月29日 星期日 17:40 |
允许迟交 | 是 | 关闭时间 | 2016年05月29日 星期日 17:40 |
输入文件 | city.in | 输出文件 | city.out |
【题目描述】友好城市(city.cpp/c/pas)
一条河从东向西流过,并把魔法世界分为南北两个部分。河的两岸各有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
5
4 5
2 4
5 2
1 3
3 1
【输出样例】
3