題目大意：
　　中國郵遞員問題。
　　給你一個(gè)無向帶權(quán)連通圖，求經(jīng)過所有邊并返回起點(diǎn)的最短路徑。

思路：
　　Edmonds-Johnson算法。
　　顯然，當(dāng)原圖為歐拉圖時(shí)，答案即為其歐拉回路的長(zhǎng)度。
　　考慮原圖不存在歐拉回路時(shí)的情況。
　　一個(gè)圖存在歐拉回路，當(dāng)且僅當(dāng)這個(gè)圖中度為奇數(shù)的點(diǎn)的個(gè)數(shù)為0。
　　然而現(xiàn)在我們的圖并不一定是歐拉圖，這就說明圖中有可能由度數(shù)為奇數(shù)的點(diǎn)。
　　顯然，我們需要重復(fù)走的邊，一定是連接這些度為奇數(shù)的點(diǎn)的。
　　我們可以用Dijkstra對(duì)這些點(diǎn)求最短路（由于數(shù)據(jù)范圍較小，用Floyd也沒關(guān)系）。
　　然后對(duì)所有點(diǎn)對(duì)之間的最短路構(gòu)建新圖。
　　再對(duì)新圖跑一般圖最小權(quán)完美匹配（用狀壓DP或者記憶化搜索）。
　　最后匹配出來的匹配就是重復(fù)走的路徑長(zhǎng)度。
　　用老圖的邊權(quán)和加上新圖的匹配就是答案。
　　本來能1A的，但是由于用了平板電視，在POJ上CE了，但是在UVa上就直接0ms0kB過。

1 #include<cstdio> 2 #include<cctype> 3 #include<vector> 4 #include<cstring> 5 #include<functional> 6 #include<ext/pb_ds/priority_queue.hpp> 7 inline int getint() { 8 register char ch; 9 while(!isdigit(ch=getchar())); 10 register int x=ch^'0'; 11 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 12 return x; 13 } 14 const int inf=0x7fffffff; 15 const int V=16; 16 struct Edge { 17 int to,w; 18 }; 19 std::vector<Edge> e[V]; 20 void add_edge(const int &u,const int &v,const int &w) { 21 e[u].push_back((Edge){v,w}); 22 e[v].push_back((Edge){u,w}); 23 } 24 int deg[V]; 25 std::vector<int> kv; 26 struct Vertex { 27 int d,id; 28 bool operator > (const Vertex &another) const { 29 return d>another.d; 30 } 31 }; 32 int n; 33 int k[V][V]; 34 __gnu_pbds::priority_queue<Vertex,std::greater<Vertex> > q; 35 __gnu_pbds::priority_queue<Vertex,std::greater<Vertex> >::point_iterator p[V]; 36 inline void Dijkstra(const int &s) { 37 int *d=k[s]; 38 q.clear(); 39 for(register int i=1;i<=n;i++) { 40 if(i!=s) { 41 p[i]=q.push((Vertex){d[i]=inf,i}); 42 } else { 43 p[i]=q.push((Vertex){d[i]=0,i}); 44 } 45 } 46 while(q.top().d!=inf) { 47 const int x=q.top().id; 48 for(register unsigned i=0;i<e[x].size();i++) { 49 const int &y=e[x][i].to; 50 if(d[x]+e[x][i].w<d[y]) { 51 d[y]=d[x]+e[x][i].w; 52 q.modify(p[y],(Vertex){d[y],y}); 53 } 54 } 55 q.modify(p[x],(Vertex){inf,x}); 56 } 57 } 58 int f[1<<16]; 59 inline void init() { 60 for(register int i=1;i<V;i++) { 61 e[i].clear(); 62 } 63 kv.clear(); 64 memset(deg,0,sizeof deg); 65 memset(f,-1,sizeof f); 66 } 67 int dfs(const int st) { 68 if(!st) return 0; 69 if(~f[st]) return f[st]; 70 f[st]=inf; 71 for(int i=1;i<=n;i++) { 72 if(!(st&(1<<i))) continue; 73 for(int j=1;j<=n;j++) { 74 if(i==j) continue; 75 if(!(st&(1<<j))) continue; 76 f[st]=std::min(f[st],dfs(st^(1<<i)^(1<<j))+k[i][j]); 77 } 78 } 79 return f[st]; 80 } 81 int main() { 82 for(;;) { 83 n=getint(); 84 if(!n) return 0; 85 init(); 86 int m=getint(); 87 int ans=0; 88 for(register int i=0;i<m;i++) { 89 const int &u=getint(),&v=getint(),&w=getint(); 90 deg[u]++,deg[v]++; 91 add_edge(u,v,w); 92 ans+=w; 93 } 94 int st=0; 95 for(register int i=1;i<=n;i++) { 96 if(deg[i]&1) { 97 kv.push_back(i); 98 st|=1<<i; 99 } 100 } 101 for(register unsigned i=0;i<kv.size();i++) { 102 Dijkstra(kv[i]); 103 } 104 ans+=dfs(st); 105 printf("%d\n",ans); 106 } 107 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/skylee03/p/7595439.html

總結(jié)

以上是生活随笔為你收集整理的[UVa10296]Jogging Trails的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。