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

Answer 2

ルートが交差する場所や都市をノードとして使用し、送信元ノードと宛先を追加して、最大フローを使用します。
ソース ノードが上にあり、終点が下にあると仮定したエッジの割り当て。最初の交差の前には、各エッジに値 1 が割り当てられます。最初の交差の後は、最も小さい番号を持つエッジに割り当てられます。の交差が選択されて値 1 が割り当てられ、残りには値 0 が割り当てられます。アルゴリズムが正しいかどうかは証明されていませんが、いくつかのブレーンストーミングの後、それは正しいはずです。私はそれを証明するのが面倒です。

Answer 3

始点と終点を 2 つの列ベクトルとして設定し、終点の値から始点の値を減算し、0 以上の経路を見つけて削除します。

Answer 4

一方では都市番号の昇順にソートし、もう一方では減少しない最長の都市番号のシーケンスを見つけて、見つかったシーケンスの長さを都市の総数から減算します。