题意：
分析：
欧拉通路:图连通；图中只有0个或2个度为奇数的结点
这题我们只需要判断选择的边构成多少个联通块， 再记录全部联通块一共有多少个奇度顶点。
然后我们在联通块中连线， 每次连接两个联通块就减少2个奇度顶点， 然后再数一下剩下的奇度顶点odd（肯定是剩下偶数个）， 因为存在两个奇度顶点的图也是欧拉通路， 我们只需要在（odd - 2）个顶点中连线使其变为偶度顶点即可。
如果本身就没有奇度顶点就不需要除了。
所以答案就是 T * （E +（联通块 - 1） + （odd - 2）/ 2））
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1007; 4 int V, E, T; 5 vector<int> G[maxn]; 6 set<int> pick; 7 int deg[maxn]; 8 bool vis[maxn]; 9 void dfs(int u){ 10 vis[u] = 1; 11 for(int i = 0; i < G[u].size(); i++){ 12 if(!vis[G[u][i]]){ 13 dfs(G[u][i]); 14 } 15 } 16 } 17 int main(){ 18 19 int kase = 1; 20 while(scanf("%d %d %d", &V, &E, &T) && V){ 21 22 memset(deg,0, sizeof(deg)); 23 memset(vis,0 , sizeof(vis)); 24 pick.clear(); 25 26 for(int i = 0; i < E; i++){ 27 int u, v; 28 29 scanf("%d %d", &u, &v); 30 deg[u]++, deg[v]++; 31 G[u].push_back(v); 32 G[v].push_back(u); 33 pick.insert(v); 34 pick.insert(u); 35 } 36 37 int part = 0; 38 int odd = 0, even = 0; 39 for(auto it = pick.begin(); it != pick.end(); it++){ 40 if(!vis[*it]){ 41 dfs(*it); 42 part++; 43 } 44 if(deg[*it] % 2 == 0){ 45 even++; 46 } 47 else odd++; 48 G[*it].clear(); 49 } 50 odd -= (part - 1) * 2; 51 52 int ans = E + part - 1; 53 54 if(odd > 2){ 55 ans += (odd -1)/2; 56 } 57 58 if(E == 0) ans = 0;//特判一下没有边的情况 59 printf("Case %d: %d ",kase++, ans * T); 60 61 } 62 return 0; 63 }