题意：给出一个国家城市个数n 所需走过道路个数e 每条道路长t 该国家任意两个城市之间都存在唯一道路长t 要求 ：找一条最短的路遍历所有所需走过的路
一开始以为是图的匹配 但是好像又无从下手
参考了其他人的做法 发现要用欧拉道路的知识
欧拉道路：如果一个联通图，形成欧拉路，那么度数为奇数的有两个，如果是欧拉环，则全部为度数为偶数的顶点。
一个图的 度数为奇数的个数一定是偶数！！！！！
当一个联通块 为一个环 或者度数为奇数的个数恰巧为两个时 不需要另外加路了 一笔画就行
当一个联通块度数超过2时 每两个奇数度的点可以用一条增加的路来连接 就可以消去两个奇数度 所以 增广路=（奇数度点的个数-2）/2
还有就是 两个不相连的联通块需要一条路连在一起 用ans表示
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define N 1005
#define inf 0x3f3f3f3f
int du[N];
vector<int>g[N];
int vis[N]; int dfs(int x)
{
int sum=;
vis[x]=;
for(int i=;i<g[x].size();i++)
{
if(!vis[ g[x][i] ])
sum+=dfs(g[x][i]);
}
if(du[x]%)
return sum+;
else
return sum;
} int main()
{
int n,e,t;
int ans;//联通块的个数
int ans1;//奇数度要补的个数
int cas=;
while(scanf("%d%d%d",&n,&e,&t)==,n)
{
for(int i=;i<=n;i++)g[i].clear();
memset(du,,sizeof du);
memset(vis,,sizeof vis);
for(int i=;i<e;i++)
{
int a,b;
scanf("%d%d",&a,&b);
du[a]++;
du[b]++;
g[a].push_back(b);
g[b].push_back(a);
}
ans=ans1=;
for(int i=;i<=n;i++)
{
if(du[i]&&!vis[i])
{
ans++;
int x=dfs(i);
if(x>)
ans1+=(x-)/;
}
}
if(ans>)
ans--;
printf("Case %d: %d\n",++cas,t*( ans+ans1+e ) );
}
return ;
}