UVa 12118 - Inspector's Dilemma(DFS判连通+欧拉回路)

昨天统计题数错联系锟神时提到了这道题,给他讲了我的思路,感觉博客写的太简略,正好百题之后准备重新理一遍博客,所以就先来写写这道题。

有v个城市,每个城市间都有道路连通,要检查e个道路,起点终点任选。输入v、e、检查每个道路的时间t。求最少总时间。

求最少总时间,感觉与UVa818切锁链中的环有些神似。

所给的e条道路是必经的,只需要找到最少的路使得给的路形成欧拉道路即可。

首先,对所有的道路判连通,假设形成了n个连通组,那么连起来就需要n-1条路。

然后,统计每组中度数为奇数的点,每一个奇数点都要构造另一条路使之度数为偶数,但是每一组仅需形成一条链而不是环,仅需形成欧拉道路而不是欧拉回路,所以统计个数要
减去链的端点2。

最后,求每组的和,减去一就是需要连成一个整体所用的道路数,加上e,总道路就求出来的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。