题解 | #Inspector's Dilemma#

题目大意：
给你V,E,T三个数字
每条边长度为T
给你V个点，每个点都两两连接
再给你E条边
让你输出包括这E条边的最短路径

思路：
欧拉道路
通过图G中每条边一次且仅一次的道路称作该图的欧拉道路。
无向图G存在欧拉道路当且仅当G是连通的且奇数度顶点不超过2个
连上这E条边
看有几个连通块就补上连通块-1数量的边
同时还要看连通块中奇数度数点是不是只有两个
不是的话要给它补上(奇数度数点-2)/2条边
注意这里奇数度数的点必定是偶数
因为无向图中所有点度数之和都是偶数
那么奇度数点之和也必定是偶数

AC代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1010;
vector<int>e[N];
int vis[N];
void dfs(int x,int &p)
{
    vis[x]=1;
    p+=e[x].size()%2;
    for(int i=0; i<e[x].size(); i++)
    {
        int y=e[x][i];
        if(!vis[y])dfs(y,p);
    }
    return;
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int V,E,T;
    int k=0;
    while(cin>>V>>E>>T)
    {
        if(!V&&!E&&!T)break;
        for(int i=1; i<=V; i++)e[i].clear();
        fill_n(vis,N,0);
        for(int i=0; i<E; i++)
        {
            int a,b;
            cin>>a>>b;
            e[a].push_back(b);
            e[b].push_back(a);
        }
        int nc=0,ans=0;//nc是连通块数量，ans表示要为奇度数点添加的边
        for(int i=1; i<=V; i++)
        {
            if(!e[i].empty()&&!vis[i])
            {
                int p=0;//找这个连通块中奇度数的点
                dfs(i,p);
                if(p>2)ans+=(p-2)/2;
                nc++;
            }
        }
        cout<<"Case "<<++k<<": "<<T*(E+ans+max(0,nc-1))<<endl;
    }
    return 0;
}