问题 1877 --布线问题

1877: 布线问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 5  解决: 4
[提交][状态][讨论版][命题人:]

题目描述

在房屋装修过程中经常会遇到各种电路线的布线问题,现给定一个每边带n 个针脚的布线通道和一个排列C。顶部的针脚i 与底部的针脚Ci 相连,其中1in,数对(i, Ci ) 称为网组。总共有n 个网组需连接或连通。假设有两个或更多的布线层,其中有一个为优先层,在优先层中可以使用更细的连线,其电阻也可能比其他层要小得多。布线时应尽可能在优先层中布设更多的网组。当且仅当两个网组之间不交叉时,它们可布设在同一层。我们的任务是尽可能在优先层中铺设最多的网组。

输入

输入文件中包含多组测试数据。每组测试数据占2行,第1行为一个正整数n1<=n<=500),表示该组数据中供选择的网组的数目;第2行为n个正整数C1,C2……Cn1<=Ci<=n)。(说明:若C2=7则表示(2,7)是一个网组)。一直输入到文件尾。

 

输出

对于每组测试数据,输出该布线排列中优先层可以铺设的最多网组数目。

样例输入

10
8 7 4 2 5 1 9 3 10 6
6
1 2 3 4 5 6

样例输出

4
6

提示

来源

 

[提交][状态]