2198: 宝典2第十一章友好城市

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:35 Solved:13

Description

【题目描述】友好城市(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

加入题单

上一题 下一题 算法标签: