d915. 3. 洗街車路線問題
d915. 3. 洗街車路線問題
內容 ：
市政府派出一輛洗街車欲清洗甲區域的街道，甲區域有 N 個加水站，2 <= N <= 1500。為了方便說明，我們將 N 個加水站名稱以正整數 1, 2, …, N 來表示。N 個加水站有街道來連接，使得洗街車可從任一個加水站出發，經由幾條街道抵達另一個加水站。我們可以用圖形來表示這些加水站跟街道的關係：節點表示加水站；而連接結點的連結線則代表連接兩個加水站之間的街道。我們以符號 (I, J) 來表示連接加水站 I 和加水站 J 的連結線，並稱街道 (I, J) 與加水站 I 和加水站 J 相接。每一條連結線 (I, J) 都結合一個權重 w(I, J) 來代表清洗 (I, J) 這條街道所要花費的時間，w(I, J) 為正整數滿足 1 <= w(I, J) <= 888。圖一有 12 個加水站，以數字1 ~ 12 來表示，而街道上的數字則代表清洗此街道所需花費的時間。令 Nodd 代表那些與奇數條街道相接的加水站個數，則甲區域有一個重要特性：Nodd 為偶數且0 <= Nodd <= 14 。在圖一的例子中，Nodd = 8 ，起始加水站為 1。
給定一個起始加水站，請寫一個程式計算洗街車從起始加水站出發，把每條街道都清洗過至少一次，再回到原起始加水站所需花費的最短時間為何？注意：這個城市中所有的街道都是雙向道，洗街車洗街時同一個加水站和街道可被洗街車重複經過。
圖二說明其中一種走法為：1 → 8 → 1 → 9 → 8 一7 → 12 → 6 → 7 → 6 → 5 → 4 → 5 → 11 → 12 → 9 → 10 → 11 → 4 → 3 → 2 → 3 → 10 → 2 → 1，可在 73 單位時間將所有街道都清洗過至少一次，然而此種走法所需的時間並非最短。事實上，此例中花費時間為最短的走法如圖三所示為 l → 8 → 9 → 1 → 9 一8 → 7 → 6 → 12 → 7 → 12 → 6 → 5 → 4 → 11 → 5 → 11 → 4 → 3 → 2 → 10 → 3 → 10 → 11 → 12 → 9 → 10 → 2 → l，所花費時間為 64 單位。
輸入說明
：
輸出說明
：
範例輸入 ：
輸入範例 1: 12 20 1 1 2 8 1 8 5 2 3 6 1 9 1 2 10 2 8 9 1 9 10 1 10 3 1 8 7 2 9 12 3 10 11 1 3 4 1 7 12 1 12 11 2 11 4 1 7 6 6 12 6 2 11 5 1 4 5 2 6 5 7 輸入範例 2: 10 9 1 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 輸入範例 3: 20 20 1 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 1 1
範例輸出 ：
輸出範例 1: 64 輸出範例 2: l8 輸出範例3 : 20
提示
：
出處
：
作法 : 最短路徑問題 搭配 最小權匹配
把所有奇數入度的點找出來，找出互相的距離，要走回 Start，
重複走過的路徑必會在這些奇數入度的點之間，在這裡使用匹配，
將這些點兩兩配對在一起。
匹配的部分使用 DP
/**********************************************************************************/
/* Problem: d915 "3. 洗街車路線問題" from 99資訊能力競賽全國決賽*/
/* Language: C (2668 Bytes) */
/* Result: AC(1ms, 417KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-11-04 18:05:54 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define oo 1000000000
typedef struct {
int x, y, v;
}Pair;
Pair Path[2250001];
int cmp(const void *i, const void *j) {
Pair *x, *y;
x = (Pair *)i, y = (Pair *)j;
if(x->x < y->x) return -1;
else if(x->x == y->x)
return x->v - y->v;
else return 1;
}
int Min(int x, int y) {
return x < y ? x : y;
}
int NodeT[1501], NodeL[1501], Q[2250001];
int Map[16][16];
void SPFA(int st, int N, int Idx) {
int i, j, k;
static int Used[1501], V[1501], QIdx;
static int DP[1501], tNode;
for(i = 1; i <= N; i++)
Used[i] = 0, V[i] = oo, DP[i] = 0;
Used[st] = 1, V[st] = 0, QIdx = 0, Q[QIdx] = st;
for(i = 0; i <= QIdx; i++) {
tNode = Q[i], Used[tNode] = 0;
for(j = 0, k = NodeL[tNode]; j < NodeT[tNode]; j++, k++) {
if(V[tNode] + Path[k].v < V[Path[k].y]) {
V[Path[k].y] = V[tNode] + Path[k].v;
if(!Used[Path[k].y]) {
Used[Path[k].y] = 1, Q[++QIdx] = Path[k].y;
}
}
}
}
for(i = 1, j = 0; i <= N; i++)
if(NodeT[i]%2)
Map[Idx][j] = V[i], j++;
}
int Best[65537], Idx;
int DP(int N, int sum) {
if(N == 0) return 0;
if(Best[N] != oo)
return Best[N];
if(Best[sum] == oo)
Best[sum] = DP(sum, 0);
int i, j, tmp;
for(i = 0; i < Idx; i++) {
if(N&(1<<i)) {
for(j = i+1; j < Idx; j++) {
if(N&(1<<j)) {
tmp = DP(N-(1<<i)-(1<<j), sum+(1<<i)+(1<<j));
Best[N] = Best[N] < tmp+Map[i][j] ? Best[N] : tmp+Map[i][j];
}
}
break;
}
}
return Best[N];
}
int main() {
int N, M, S, i, j;
while(scanf("%d %d %d", &N, &M, &S) == 3) {
int Sum = 0;
for(i = 1; i <= N; i++)
NodeL[i] = oo, NodeT[i] = 0;
for(i = 0; i < M; i++) {
scanf("%d %d %d", &Path[i].x, &Path[i].y, &Path[i].v);
Path[M+i].x = Path[i].y;
Path[M+i].y = Path[i].x;
Path[M+i].v = Path[i].v;
Sum += Path[i].v;
}
qsort(Path, 2*M, sizeof(Pair), cmp);
for(i = 0, M *= 2; i < M; i++) {
NodeL[Path[i].x] = Min(i, NodeL[Path[i].x]);
NodeT[Path[i].x] ++;
}
Idx = 0;
for(i = 1; i <= N; i++) {
if(NodeT[i]%2)
SPFA(i, N, Idx), Idx++;
}
for(i = (1<<Idx)-1; i >= 0; i--)
Best[i] = oo;
Best[0] = 0;
printf("%d\n", DP((1<<Idx)-1, 0)+Sum);
}
return 0;
}