https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3270
2017年的第一题。
题意:给出必须要经过的边，找一条经过所有边的最短道路。
一开始一点想法都没有，后来网上看了下才明白是要用dfs和欧拉回路来做的。
欧拉回路是这样说的：如果一个无向图是连通的，且最多只有两个奇点，则一定存在欧拉道路。如果有两个奇点，则必须从其中一个奇点出发，另一个奇点终止；如果奇点不存在，则可以从任意点出发，最终一定会回到该点。
对于这道题，用dfs可以求出连通块来，由于是要形成欧拉道路就可以了，所以可以存在两个奇点，但是如果超过了两个奇点，那么每个奇点就得多加一条边使之成为偶数点，最终只剩下两个奇点，那么就可以形成欧拉道路了。
这道题我错了好久，在输入的时候我是这么写的while (cin >> v >> e >> t && v && e && t )，但其实只要while (cin >> v >> e >> t && v )就可以了。
通过这道题，终于好好的了解了下欧拉回路。
#include<iostream>
#include<string>
#include<cstring>
using namespace std; const int maxn = ; int G[maxn][maxn];
int v;
int degree[maxn];
int ans; void dfs(int u)
{
for (int i = ; i <= v; i++)
{
if (G[u][i])
{
degree[u]++; //统计每个结点的度数
degree[i]++;
G[u][i] = G[i][u] = ;
ans++;
dfs(i);
}
}
} int main()
{
int e, t;
int x, y;
int kase = ;
while (cin >> v >> e >> t && v )
{
memset(G, , sizeof(G));
for (int i = ; i < e; i++)
{
cin >> x >> y;
G[x][y] = ;
G[y][x] = ;
}
int count = ;
ans = ;
for (int i = ; i <= v; i++)
{
for (int j = ; j <= v; j++)
{
if (G[i][j])
{
memset(degree, , sizeof(degree));
count++; //统计连通块
dfs(i);
int jidian = ; //计算出奇点的个数
for (int i = ; i <= v; i++)
{
if (degree[i] % == ) jidian++;
}
if (jidian > ) ans += (jidian - )/;
}
}
}
ans = ans + count;
if (ans) ans = ans - ;
cout<<"Case "<<++kase<<": "<<ans*t<<endl;
}
return ;
}