算法题 航线交叉

Question

航线交叉有一条河道，河道南北两侧分别有n个城市，0 < n < 100，南北的城市之间有航线相连，但是有的航线是有交叉的，容易产生事故。现在已知每个城市有且只有一条航线与对岸的某个城市相连，希望减少一些航线来避免事故，请问减少的最小航线数是多少？例如上图中，需要去掉的航线数是3，分别是1-2, 4-4, 6-3这三条（其中前面一个数字表示北面的城市号，后一个数字表示南面的城市号）。输入的第一个数是城市数n，接下来2个数为一组，有n组城市航线对，第一个数字代表北面的城市号，后一个数字代表南面的城市号。输出为需要减少的最少航线数。样例输入：6 1 2 2 1 3 5 4 4 5 6 6 3样例输出：3

Answer 1

遍历1-n的节点计算每个城市的相交数量，去掉最多者，重复多次直到无相交为止。
计算相交的方法：
a b c d
boolean = (a-c)*(c-d)<0.

Answer 2

以航线交叉的地方和城市为节点，添加一个源节点和终点，用最大流。
边的赋值，假设源节点在上，终点在下，在第一次交叉之前，每条边赋值1，第一次交叉之后，选择一条交叉次数最少的赋值1，其余赋值零。还没有证明算法是对的，不过脑补了一下，应该是对的，懒得证了。

Answer 3

将起点的终点 设为两列向量，然后用终点值减去起点值，找到不小于0的航线 去掉。

Answer 4

以一侧城市编号递增排序，找对岸城市编号的最长不下降序列，用总城市数减去找到的序列长度就可以了。