UVa 10296 : Jogging Trails
問題リンク:http://uva.onlinejudge.org/external/102/10296.html
問題概要:
n個のノードとm個のエッジが与えられる
任意のノードからスタートして全ての辺を少なくとも1回は通った後に再度
スタートしたノードに戻ってくるのに必要な最小のコストを求めよ
辺は両方向に移動できる
制約:
・n <= 15
・m < 1000
解法:
オイラー閉路である場合、すべての辺のコストの総和が答えとなる
そうでない場合、次数が奇数の頂点が偶数個存在するはずである
それらの奇頂点だけで完全グラフを作る
そのグラフのエッジのコストはもとのグラフでのそれらのノード間の最短コストとする
この完全グラフの最小マッチングを求め、その結果を新たな辺として追加する
こうすることでオイラーグラフでなかったグラフをオイラーグラフにする亊ができる
オイラーグラフになったのであれば後は全ての辺のコストの総和をとって出力すれば良い
完全グラフの最小マッチングはノード数が少ないのでビットDPで計算する
コード:
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<vector> #include<cassert> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) #define inf (1<<29) #define MAX 16 using namespace std; struct P { int to,cost; P(int to=inf,int cost=inf):to(to),cost(cost){} }; int n,m,N; vector<P> G[MAX]; int mincost[MAX][MAX]; int memo[(1<<MAX)]; /*以下はメモ化再帰バージョン void rec(vector<int> &odd,int state,int cost) { if(state == (1<<N)-1) { memo[state] = min(memo[state],cost); return; } rep(i,N) { if((state>>i) & 1)continue; REP(j,i+1,N) { if((state>>j) & 1)continue; int next_state = state | (1<<i) | (1<<j); int next_cost = cost + mincost[odd[i]][odd[j]]; if(next_cost < memo[next_state]) { memo[next_state] = next_cost; rec(odd,next_state,next_cost); } } } } */ int main() { while(scanf("%d",&n),n) { int ans = 0; scanf("%d",&m); rep(i,n)G[i].clear(); rep(i,n)rep(j,n)mincost[i][j] = (i==j?0:inf); rep(i,m) { int s,t,c; scanf("%d %d %d",&s,&t,&c); s--,t--; mincost[s][t] = mincost[t][s] = min(c,mincost[s][t]); G[s].push_back(P(t,c)); G[t].push_back(P(s,c)); ans += c; } vector<int> odd; rep(i,n) { if(G[i].size()%2) { odd.push_back(i); } } rep(k,n)rep(i,n)rep(j,n) mincost[i][j] = min(mincost[i][j], mincost[i][k]+mincost[k][j]); N = odd.size(); rep(i,(1<<N))memo[i] = inf; memo[0] = 0; rep(state,(1<<N)) { rep(sp,N) { if((state>>sp) & 1)continue; rep(ep,N) { if(sp == ep)continue; if((state>>ep) & 1)continue; memo[state|(1<<sp)|(1<<ep)] = min(memo[state|(1<<sp)|(1<<ep)], memo[state]+mincost[odd[sp]][odd[ep]]); } } } //rec(odd,0,0); cout << ans + memo[(1<<N)-1] << endl; } return 0; }