UVa 12118 - Inspector's Dilemma(DFS 연결 판정 + 오라 리턴)

어제 통계 문제가 틀리고 쿤신과 연결될 때 이 문제를 언급해서 그에게 나의 생각을 말해 주었다. 블로그를 너무 간략하게 쓴 것 같아서 마침 백 문제 후에 블로그를 다시 한 번 정리하려고 하기 때문에 이 문제를 먼저 썼다.
v개 도시가 있고 모든 도시 간에 도로가 연결되어 있으며 e개 도로를 검사하고 기점 종점에서 선택해야 한다.v, e, 모든 도로를 검사하는 시간 t를 입력하십시오.최소 총 시간을 구하다.
최소 총 시간을 구하면 UVa818의 쇠사슬 속의 고리와 약간 비슷하게 느껴진다.
주어진 e개의 길은 반드시 거쳐야 한다. 최소한의 길을 찾아서 주어진 길이 오라의 길을 형성하기만 하면 된다.
우선, 모든 도로에 대해 연결을 판정하고 n개의 연결조가 형성되었다고 가정하면 연결하려면 n-1개의 길이 필요하다.
그 다음에 각 그룹의 도수가 홀수인 점을 통계하고 각 홀수점은 다른 길을 만들어 짝수를 만들어야 한다. 그러나 각 그룹은 고리가 아닌 체인을 형성하고 오로라 도로를 형성해야 하기 때문에 통계 개수는 체인의 단점 2를 빼야 한다.
마지막으로 각 조의 합을 구하고 하나를 빼면 하나의 전체가 사용하는 도로 수를 연결해야 하고 e를 더하면 전체 도로가 구한다.

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=1010;
int v,e,t,cnt;
bool vis[maxn];
vector<int> g[maxn];
bool read(){
    cin>>v>>e>>t;
    if(!v&&!e&&!t) return false;
    for(int i=0;i<maxn;++i)
        g[i].clear();
    memset(vis,0,sizeof(vis));
    for(int i=0;i<e;++i){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    return true;
}
void dfs(int cur){
    if(vis[cur]) return;
    vis[cur]=true;
    cnt+=(int)g[cur].size()&1;//         。
    for(int i=0;i<g[cur].size();++i)
        dfs(g[cur][i]);//DFS   。
    return;
}
int solve(){
    int ans=0;
    for(int i=1;i<=v;++i){
        if(!vis[i]&&!g[i].empty()){
            cnt=0;
            dfs(i);
            ans+=max(cnt,2);//        2   ，        。
        }
    }
    return t*(max(ans/2-1,0)+e);//                    ，      e   。
}
int main(){
    ios::sync_with_stdio(false);
    int k=0;
    while(read())
        cout<<"Case "<<++k<<": "<<solve()<<endl;
    return 0;
}