航线交叉
有一条河道,河道南北两侧分别有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
遍历1-n的节点计算每个城市的相交数量,去掉最多者,重复多次直到无相交为止。
计算相交的方法:
a b c d
boolean = (a-c)*(c-d)<0.
以航线交叉的地方和城市为节点,添加一个源节点和终点,用最大流。
边的赋值,假设源节点在上,终点在下,在第一次交叉之前,每条边赋值1,第一次交叉之后,选择一条交叉次数最少的赋值1,其余赋值零。还没有证明算法是对的,不过脑补了一下,应该是对的,懒得证了。
将起点的终点 设为两列向量,然后用终点值减去起点值,找到不小于0的航线 去掉。
以一侧城市编号递增排序,找对岸城市编号的最长不下降序列,用总城市数减去找到的序列长度就可以了。