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

Traversez les nœuds 1 à n pour calculer le nombre d'intersections dans chaque ville, supprimez-en le plus et répétez plusieurs fois jusqu'à ce qu'il n'y ait plus d'intersections.
Méthode de calcul de l'intersection :
a b c d
boolean = (a-c)*(c-d)<0.

Answer 2

Utilisez les lieux et les villes où les itinéraires se croisent comme nœuds, ajoutez un nœud source et une destination et utilisez le flux maximum.
Assignation des arêtes, en supposant que le nœud source est en haut et le point final est en bas Avant le premier croisement, chaque arête se voit attribuer une valeur de 1. Après le premier croisement, celle avec le moins de numéro. des croisements est sélectionné et reçoit une valeur de 1, et le reste reçoit une valeur de zéro. Il n'a pas été prouvé que l'algorithme est correct, mais après quelques réflexions, il devrait être correct, et je suis trop paresseux pour le prouver.

Answer 3

Définissez le point de départ et le point final sous forme de deux vecteurs colonnes, puis soustrayez la valeur du point de départ de la valeur du point final, recherchez l'itinéraire qui n'est pas inférieur à 0 et supprimez-le.

Answer 4

Triez par ordre croissant des numéros de ville d'un côté, trouvez la séquence non décroissante la plus longue de numéros de ville de l'autre côté et soustrayez la longueur de la séquence trouvée du nombre total de villes.