java - 算法题 航线交叉

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
부울 = (a-c)*(c-d)<0.

Answer 2

경로가 교차하는 장소와 도시를 노드로 사용하고, 출발지와 목적지를 추가하고 최대 흐름을 활용하세요.
원본 노드가 위쪽에 있고 끝점이 아래쪽에 있다고 가정하여 가장자리 할당 첫 번째 교차 전에 각 가장자리에는 값 1이 할당됩니다. 첫 번째 교차 후에는 번호가 가장 적은 것입니다. 교차점의 개수가 선택되어 값 1이 할당되고 나머지에는 값 0이 할당됩니다. 알고리즘이 정확하다는 것은 입증되지 않았지만 몇 가지 브레인스토밍 후에는 정확해야 하는데 이를 증명하기에는 너무 게으릅니다.

Answer 3

시작점과 끝점을 두 개의 열 벡터로 설정한 후 끝점 값에서 시작점 값을 뺀 후 0보다 작지 않은 경로를 찾아 제거합니다.

Answer 4

한쪽은 도시 번호를 오름차순으로 정렬하고, 다른 쪽은 감소하지 않는 가장 긴 도시 번호 순서를 찾아 찾은 순서 길이를 전체 도시 수에서 뺍니다.