根据欧拉回路的性质算出来的
http://blog.csdn.net/wcr1996/article/details/43309671
看了大神的，写下自己理解
假设一开始只有题中给定的限定的边，若不联通，就一条一条边加，加边要加在两个奇点之间，但是题目只要求求至少有几条边，所以只需算一下就好了。
计算所有奇点数，连接n个点最少n-1条边若没有E边的限制，且一共只能有两个奇点。
第一次发现用vector记录边特别方便..
#include<iostream>
#include<cstring>
#include<set>
#include<vector>
#include<cstdio>
#include<queue>
#include<cctype>
using namespace std;
const int maxn=1005;
int n,w,vis[maxn],cnt,k;
vector<int> G[maxn];
void dfs(int u)
{if(vis[u]) return;vis[u]=1;cnt+=G[u].size()%2==1?1:0; //记录奇点个数for(int v=0;v<G[u].size();v++)dfs(G[u][v]);
}
int solve()
{int ans=0;memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)if(!vis[i]&&!G[i].empty()){cnt=0;dfs(i); //每一连通组的奇点数保存在cnt中 ans+=max(cnt,2);} //ans中是所有图的奇点数 return max(ans/2-1,0)+k; /*根据欧拉道路，要形成一笔画(而且是链式的)，图中只能有两个奇点已经知道有几个奇点，且连一条边消去2个奇点，一共有ans个奇点，所以要加(ans/2-1)个边，最后只剩下起点，结尾两个奇点 */
}
int main()
{int kase=0;while(scanf("%d%d%d",&n,&k,&w)&&n){memset(G,0,sizeof(G));for(int i=0;i<k;i++){int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);G[y].push_back(x);}int ans=solve();printf("Case %d: %d\n",++kase,ans*w);}}