500pt
50個點的地圖，從0開始按照順序訪問一系列點（不超過50個），訪問順序給出，一個點可能訪問多次。某些點停著若干輛汽車。可以走路，也可以開車。開車的速度比走路快。但是限定一輛汽車只能使用一次，也就是下車后這輛車就作廢。問按要求訪問完所有點的最短總耗時。
先floyd求每對點之間走路時間和開車時間。對于訪問順序中的每一步，使用每輛車都有個節省的時間。這就相當于建個二分圖，左邊x是訪問順序中的每一步，右邊y是每一輛車。xi與yj的邊權就是第i步使用第j輛車能節省的時間。
最后結果就是總的走路時間減去最大權匹配。
[floyd最短路 二分圖最大權匹配]
posted on 2011-05-12 11:22
wolf5x 閱讀(297)
評論(0) 編輯 收藏 引用 所屬分類:
topcoder