【紫书】Uva 12118 检查员的难题

检查员的难题"/>

【紫书】Uva 12118 检查员的难题

紫书习题6.14 Inspector’s Dilemma 检查员的难题

某国家有 V ( V ≤ 1000 ) V(V\leq1000) V(V≤1000)个城市。每两个城市之间都有一条道路直接相连，每一条道路长度都为T。现在需要找一条最短的道路（起点和终点任意），使得该道路经过E条指定的边。

比如，如果 V = 5 ， E = 3 ， T = 1 ， V=5，E=3，T=1， V=5，E=3，T=1，指定的三条边是1-2，1-3和4-5，那么最短长度为4*1=4。会有多组 V , E , T V,E,T V,E,T，输入以0 0 0结束。

样例输入：

5 3 1
1 2
1 3
4 5
4 4 1
1 2
1 4
2 3
3 4
0 0 0

样例输出：

Case 1: 4
Case 2: 4

第一反应可能会想到bfs，因为是要求一条最短的路径。但是仔细想想bfs很难下手，不知道起点，而且每次有 V − 1 V-1 V−1条道路可以选择，搜索目标过于庞大。但仔细一想，这其实是个图论的问题，每条边走一遍的问题，不就是欧拉道路问题吗？复习一下欧拉道路和回路的条件：

无向图欧拉回路：所有顶点的度数均为偶数
无向图欧拉道路：有且仅有两个顶点度数为奇数
有向图欧拉回路：所有顶点入度等于出度
有向图欧拉道路：只有两个点入度不等于出度，而且一个点入度=出度+1，另一个出度=入度+1
另外，当然都要是连通图。

假设给定我们的 E E E条边已经是连通图了。首先图论里面一个简单的结论，由握手定理，所有点度数之和肯定是偶数，换言之，肯定只有偶数个奇数度数节点。那么，如果当前奇数节点的个数 r < = 2 r<=2 r<=2，那是欧拉道路/回路，就只需要走过这 E E E条边就可以了。否则， r > 2 r>2 r>2，我们需要消去一些奇度数节点。由于两两之间都有边，所以需要增加 r − 2 2 \frac{r-2}{2} 2r−2​条边。

这是连通图的情况。对于不连通图，假设有 n n n个连通子图。对每个连通子图都像如上处理，然后就需要把 n n n个子图串起来，显然只需要在子图与子图之间，前一个图的终点到后一个图的起点之间加一条边即可，共需要 n − 1 n-1 n−1条边。所以总的思路是：对 E E E条边建图，然后dfs，得到 n n n个连通子图，每个子图内计算奇度数节点个数 r r r，累加 r − 2 2 \frac{r-2}{2} 2r−2​，最后加上 n − 1 n-1 n−1。

代码如下所示。要注意几个细节问题：

• 示例代码写的很精简，因为建完E的图之后，每个子图内计算奇度节点个数的过程可以在dfs的同时进行。
• 建图可以用邻接表，这样可以轻松得到点的度数。
• 注意边界条件的处理。如果奇度节点个数 r = 0 r=0 r=0， r − 2 2 = − 1 \frac{r-2}{2}=-1 2r−2​=−1，需要变成0。同样的，还要考虑 E = 0 E=0 E=0时，连通分量数 n = 0 n=0 n=0，也需要变成0。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <stack>
using namespace std;
int V,E,T,kase=1;
int vis[1024];
vector<int> G[1024];
int dfs(int u){vis[u]=1;int l=G[u].size(),cnt=l%2;for(int i=0;i<l;i++){if(!vis[G[u][i]]){cnt+=dfs(G[u][i]);}}return cnt;
}
int main() {while((cin>>V>>E>>T)&&(V||E||T)){memset(vis,0,sizeof(vis));for(int i=0;i<1024;i++) G[i].clear();for(int i=0;i<E;i++){int u,v;cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}int n=0,sum=E;for(int i=1;i<=V;i++){if(!vis[i]&&G[i].size()){n++;sum+=max(0,(dfs(i)-2)/2);}}printf("Case %d: %d\n",kase++,T*(max(0,sum+n-1)));}return 0;
}