NTUJ 1021 Highway Patrol

36916    1021 - Highway Patrol    poao899    Accepted    C++    0.030    2010-09-05 19:41:21                            .



好題欸@@



題意：

一個大都會內有N座城市(<=100)，有M條單行道(<=1,000)

每個單行道可以用一個數組(u, v, p, s, x)表示，表示有一條道路從u往v，

如果要派軍隊巡邏要花費p的代價、裝監視器要s的代價 (0 <= p,s <= 1,000,000)

x代表這條道路的重要性，1表示極為重要，不可以用監視器。


因為這個大都會治安很差，每條道路都必須選擇上述兩種方式之一維持治安品質。

但是，每個軍隊巡邏完了要能回到自己的城市休息，所以我們希望每個城市出分枝度 == 入分枝度。

而且，市民們也不希望看到一個全部僅由監視器戍守的城市，所以至少得有一條路是巡邏。


問最少需要花多少錢滿足以上要求。





Input:

第一行有一個數字T表示測資筆數(T <= 70)

每筆測資第一行是N, M，接下來M行每行有五個數字u, v, p, s, x。


Output:

第i筆測資輸出Case [i]: [cost]

[i]表示測資筆數，[cost]表示你所花的錢，無解請用"impossible取代"。



Sample input:

3
4 5
1 2 10 25 0
2 3 10 5 0
3 1 10 5 0
2 4 10 5 0
4 3 30 5 0
4 5
1 2 10 25 0
2 3 10 5 0
3 1 10 5 0
2 4 10 5 0
4 3 30 5 1
2 1
1 2 10 25 1

Sample output:
Case 1: 40
Case 2: 65
Case 3: impossible























=================Solution================





簡單的先捏一下，flow。





因為把這個問題轉化一下可以想到，你可以假設一開始全部監視，那這樣總cost是Σ(si)。

然後每把一個邊變成巡邏的cost會是(pi-si)。

而且最後答案一定巡邏的邊會形成好幾個環。

所以就一直找全局最小環加上去，加到那個環是正的為止。

進一步會發現，變成有負圈的圖形每次尋找全局最小簡單環。不過很可惜這個題目沒多項式作法。



所以要換一個想法。


可以先把p便宜的邊先巡邏、s便宜的邊先監視。

然後建起來可替換邊以及他的替換代價，容量都是1

然後對每個點，檢查有幾個巡邏出發/幾個巡邏回來   其中的相差就建到S/E，cost=0，容量是差。

作一次帶權flow，算出答案...



然後還要檢查答案是否合法：如果==Σ(si)那就表示你一個邊都沒取

所以Warshall一次，找出最小圈輸出