java - 算法题 航线交叉
PHPz
PHPz 2017-04-17 17:42:54
0
4
396

航线交叉
有一条河道,河道南北两侧分别有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

PHPz
PHPz

学习是最好的投资!

全員に返信 (4)
洪涛

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

いいねを押す+0
    刘奇

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

    いいねを押す+0
      左手右手慢动作

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

      いいねを押す+0
        伊谢尔伦

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

        いいねを押す+0
          最新のダウンロード
          詳細>
          ウェブエフェクト
          公式サイト
          サイト素材
          フロントエンドテンプレート
          私たちについて 免責事項 Sitemap
          PHP中国語ウェブサイト:福祉オンライン PHP トレーニング,PHP 学習者の迅速な成長を支援します!