Description
You are given undirected weighted graph. Find the length of the shortest cycle which starts from the vertex 1 and passes throught all the edges at least once. Graph may contain multiply edges between a pair of vertices and loops (edges from the vertex to itself).
Input
The first line of the input contains two integers n and m (1 ≤ n ≤ 15, 0 ≤ m ≤ 2000), n is the amount of vertices, and m is the amount of edges. Following m lines contain edges as a triples x, y, w (1 ≤ x, y ≤ n, 1 ≤ w ≤ 10000), x, y are edge endpoints, and w is the edge length.
Output
Output minimal cycle length or -1 if it doesn't exists.
Examples
Input
3 3
1 2 1
2 3 1
3 1 1
Output
3
Input
3 2
1 2 3
2 3 4
Output
14
正解：状压DP
解题报告：
考虑度数为偶数的点不需要被考虑，只需要考虑度数为奇数的情况。首先每条边必须要访问一次，所以所有边权加起来就是答案的初值。
然后度数为奇数的点就需要访问之前已经走过的边。我们考虑两个度数为奇数的点可以组合一下，变成度数为偶数的点，相当于是在这两个点之间新连了一条边，我们可以floyd预处理一下两点之间的最短路。然后状压，状态表示当前哪些结点的度数为奇数，然后枚举每次连哪两条边就可以了。
1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector> 10 #include <queue> 11 #include <map> 12 #include <set> 13 using namespace std; 14 typedef long long LL; 15 const int inf = (1<<29); 16 const int MAXN = 30; 17 const int MAXS = (1<<20); 18 int n,m,ans,end; 19 int w[MAXN][MAXN]; 20 int d[MAXN],f[MAXS]; 21 22 inline int getint() 23 { 24 int w=0,q=0; char c=getchar(); 25 while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 26 while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w; 27 } 28 29 inline void work(){ 30 n=getint(); m=getint(); int x,y,z,now; if(m==0) { printf("0"); return ; } 31 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) w[i][j]=inf; 32 for(int i=1;i<=m;i++) { 33 x=getint(); y=getint(); z=getint(); 34 ans+=z; d[x]++; d[y]++; 35 if(w[x][y]>z) w[x][y]=z,w[y][x]=z; 36 } 37 for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) if(i!=k) for(int j=1;j<=n;j++) if(i!=j && j!=k) w[i][j]=min(w[i][j],w[i][k]+w[k][j]); 38 for(int i=2;i<=n;i++) if(d[i]!=0 && w[1][i]==inf) { printf("-1"); return ; } 39 for(int i=1;i<=n;i++) if(d[i]&1) end|=(1<<(i-1)); 40 for(int i=0;i<=end;i++) f[i]=inf; f[end]=0; 41 for(int i=end;i>0;i--) { 42 if(f[i]==inf) continue; 43 for(int j=1;j<=n;j++) { 44 if(((1<<(j-1))&i )==0) continue; 45 for(int k=1;k<=n;k++) { 46 if(( (1<<(k-1))&i )==0) continue; now=i^(1<<(k-1))^(1<<(j-1)); 47 f[now]=min(f[now],f[i]+w[j][k]); 48 } 49 } 50 } 51 ans+=f[0]; printf("%d",ans); 52 } 53 54 int main() 55 { 56 work(); 57 return 0; 58 }