【题意】：给出一副无向图，n个点m条边，每条边上都有一个权值，表示通过这条边的费用。现在问任选一个点i开始遍历完所有边至少一次回到i的最小费用是多少。
【题解】：先累加一次所有边的费用sum，然后保留奇度的点，对于每两个奇度的点连边，费用为点到点的最短距离，求一次最小匹配res。最后答案为sum+res。
对于用km求最小匹配，把边权取反再加上一个inf，最后减回去即可，没边的权值为0。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "set"
13 #include "utility"
14 using namespace std;
15 typedef pair<int, int> pii;
16 #define pb push_back
17 #define mp make_pair
18 #define fi first
19 #define se second
20 #define sof(x) sizeof(x)
21 #define lc(x) (x << 1)
22 #define rc(x) (x << 1 | 1)
23 #define lowbit(x) (x & (-x))
24 #define ll long long
25 #define MAX 110
26 #define maxn 110
27 int n, m;
28 const int inf = 100000000;
29 int g[MAX][MAX];
30
31 int d[MAX];
32 int maz[maxn][maxn], lx[maxn], ly[maxn], match[maxn], sy[maxn], slack[maxn], sx[maxn];
33 int nx, ny;
34 int q[maxn], tot;
35 bool dfs(int t) {
36 sx[t] = 1;
37 for (int i = 1; i <= ny; ++i) {
38 if (sy[i])continue;
39 if (maz[t][i] == lx[t] + ly[i]) {
40 sy[i] = 1;
41 if (match[i] == -1 || dfs(match[i])) {
42 match[i] = t;
43 return 1;
44 }
45 } else slack[i] = min(slack[i], lx[t] + ly[i] - maz[t][i]);
46 }
47 return 0;
48 }
49 void Change() {
50 int Min = inf;
51 for (int i = 1; i <= ny; ++i)
52 if (!sy[i]) Min = min(Min, slack[i]);
53 for (int i = 1; i <= nx; ++i)
54 if (sx[i]) lx[i] -= Min;
55 for (int i = 1; i <= ny; ++i) {
56 if (sy[i]) ly[i] += Min;
57 else slack[i] -= Min;
58 }
59 }
60 int KM() {
61 int ans = 0;
62 memset(match, -1, sizeof (match));
63 for (int i = 1; i <= nx; ++i) {
64 for (int j = 1; j <= ny; ++j)
65 slack[j] = inf;
66 while (1) {
67 memset(sy, 0, sizeof (sy));
68 memset(sx, 0, sizeof (sx));
69 if (dfs(i)) break;
70 Change();
71 }
72 }
73 for (int i = 1; i <= ny; ++i)
74 if(match[i] != -1) ans += inf - maz[match[i]][i];
75 return ans / 2;
76 }
77 void build() {
78 memset(maz, 0, sizeof (maz));
79 nx = tot;
80 ny = tot;
81 for(int i = 0; i < tot; i++)
82 for(int j = 0; j < tot; j++) {
83 if(i != j) maz[i+1][j+1] = inf - g[q[i]][q[j]];
84 }
85 memset(ly, 0, sizeof (ly));
86 for (int i = 1; i <= nx; ++i) {
87 lx[i] = -inf;
88 for (int j = 1; j <= ny; ++j)
89 lx[i] = max(lx[i], maz[i][j]);
90 }
91 }
92
93 int floyd() {
94 for(int k = 1; k <= n; k++)
95 for(int i = 1; i <= n; i++)
96 for(int j = 1; j <= n; j++)
97 g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
98 }
99
100 int main() {
101 int T, x;
102 scanf("%d", &T);
103 while(T--) {
104 scanf("%d%d", &n, &m);
105 for(int i = 1; i <= n; i++) {
106 for(int j = 1; j <= n; j++)
107 g[i][j] = inf;
108 g[i][i] = 0;
109 }
110 int ans = 0;
111 memset(d, 0, sizeof(d));
112 for(int i = 0; i < m; i++) {
113 int u, v, w;
114 scanf("%d%d%d", &u, &v, &w);
115 ans += w;
116 g[u][v] = g[v][u] = w;
117 d[u]++, d[v]++;
118 }
119 tot = 0;
120 for(int i = 1; i <= n; i++)
121 if(d[i] & 1) q[tot++] = i;
122 floyd();
123 build();
124 int res = KM();
125 cout << ans + res << endl;
126 scanf("%d", &x);
127 if(x == -1) break;
128 }
129
130 return 0;
131 }
132