|
|
## [$POJ$ $1300$ $Door Man$](http://poj.org/problem?id=1300)
|
|
|
|
|
|
### 一、题目描述
|
|
|
你是一座大庄园的管家。庄园有很多房间，编号为$0、1、2、3$，…。你的主人是一个心不在焉的人，经常沿着走廊随意地把房间的门打开。多年来，你掌握了一个诀窍：沿着一个通道，穿过这些大房间，并把房门关上。你的问题是能否找到一条路径经过所有开着门的房间，并使得：
|
|
|
- 1 通过门后立即把门关上
|
|
|
- 2 关上了的门不再打开
|
|
|
- 3 最后回到你自己的房间（房间$0$），并且所有的门都已经关闭了。
|
|
|
|
|
|
在本题中，给定房间列表，及连通房间的、开着的门，并给定一个起始房间，判断是否存在这样的一条路径。不需要输出这样的路径，只需判断是否存在。假定任意两个房间之间都是连通的（可能需要经过其他房间）。
|
|
|
|
|
|
**输入描述**：
|
|
|
输入文件包含多个（最多可达$100$个）测试数据，每个测试数据之间没有空行隔开。
|
|
|
每个测试数据包括$3$ 部分：
|
|
|
起始行－ 格式为`START M N`，其中 $M$ 为管理员起始所处的房间号，$N$ 为房间的总数（$1≤N≤20$）；
|
|
|
房间列表－ 一共$N$ 行，每行列出了一个房间通向其他房间的房间号（只需列出比它的号码大的房间号，可能有多个，按升序排列），比如房间$3$ 有门通向房间$1、5、7$，则房间$3$ 的信息行内容为`5 7`，第一行代表房间$0$，最后一行代表行间$N-1$。有可能有些行为空行，当然最后一行肯定是空行，因为$N-1$ 是最大的房间号；两个房间之间可能有多扇门连通。终止行－内容为`END`。
|
|
|
输入文件最后一行是`ENDOFINPUT`，表示输入结束。
|
|
|
|
|
|
**输出描述**：
|
|
|
每个测试数据对应一行输出，如果能找到一条路关闭所有的门，并且回到房间$0$，则输出`YES
|
|
|
X`，`X` 是他关闭的门的总数，否则输出`NO`。
|
|
|
|
|
|
### 二、前置知识
|
|
|
|
|
|
#### $Q$:如何处理带空格的字符串输入？
|
|
|
```cpp {.line-numbers}
|
|
|
#include <iostream>
|
|
|
#include <sstream> //istringstream 必须包含这个头文件
|
|
|
#include <string>
|
|
|
using namespace std;
|
|
|
int main() {
|
|
|
string source = "i an a boy";
|
|
|
|
|
|
// 声明一个字符串输入流
|
|
|
istringstream sin;
|
|
|
// 将字符串导入到sin输入流中
|
|
|
sin.str(source);
|
|
|
|
|
|
// 分离的方法1
|
|
|
string s;
|
|
|
while (sin >> s) {
|
|
|
cout << s << endl;
|
|
|
}
|
|
|
cout << "===============================" << endl;
|
|
|
|
|
|
// 重复使用必须先清空
|
|
|
sin.clear();
|
|
|
// 重新加载，准备二次输入，或者sin的重用
|
|
|
sin.str(source);
|
|
|
string a, b, c, d;
|
|
|
sin >> a >> b >> c >> d;
|
|
|
cout << a << endl;
|
|
|
cout << b << endl;
|
|
|
cout << c << endl;
|
|
|
cout << d << endl;
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### 二、解题思路
|
|
|
|
|
|
|
|
|
以房间为顶点、连接房间之间的门为边构造图。根据题目的意思，输入文件中每个测试数据所构造的图都是连通的。本题实际上是判断一个图中是否存在欧拉回路或欧拉通路，要分两种情况考虑：
|
|
|
|
|
|
- 1 如果所有的房间都有偶数个门（通往其他房间），那么有欧拉回路，可以从$0$ 号房间出发，回到$0$ 号房间。但是这种情况下，出发的房间必须为$0$，因为要求回到$0$ 号房间。例如，第$1$ 个测试数据所对应的图为图$5.6(a)$，图中有浅色阴影的顶点（即顶点$0$），表示管家初始时所处的房间；在该测试数据中，管家可以回到$0$号房间。
|
|
|
|
|
|
2) 有两个房间的门数为奇数，其余的都是偶数，如果出发的房间和$0$号房间的门数都是奇数，那么也可以从出发的房间到达$0$号房间，并且满足题目要求。但是不能从房间$0$出发，必须从另一个门数为奇数的房间出发。例如第$2、3$ 个测试数据就是这种情形，对应的图为图($b$)和图($c$)，输出的结果分别是`NO`和`YES 7`。对于庄园的其他情形，都是不能完成题目中所要求的任务的，所以直接输出`NO`。
|
|
|
|
|
|
本题的难点在于输入数据的处理：可以使用$sscanf$函数处理数据。
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <cstdio>
|
|
|
#include <iostream>
|
|
|
#include <string>
|
|
|
#include <sstream>
|
|
|
#include <cstring>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 20;
|
|
|
int m, n, d[N];
|
|
|
|
|
|
int main() {
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("POJ1300.in", "r", stdin);
|
|
|
#endif
|
|
|
// 加快读入
|
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
|
string s;
|
|
|
while (getline(cin, s), s != "ENDOFINPUT") {
|
|
|
memset(d, 0, sizeof d); // 多组测试数据，清空度数组
|
|
|
|
|
|
istringstream sin;
|
|
|
sin.str(s); // 用s输入进行构建
|
|
|
sin >> s >> m >> n; // 进1出3
|
|
|
|
|
|
int cnt = 0;
|
|
|
for (int i = 0; i < n; i++) {
|
|
|
getline(cin, s); // 读取整行
|
|
|
if (!s.size()) continue; // 如果本行输入是空的，那么处理下一行
|
|
|
sin.clear(); // istringstream这东西如果想重复使用，需要先清空
|
|
|
sin.str(s); // 用s输入进行构建
|
|
|
int j;
|
|
|
while (sin >> j) { // 循环输出j
|
|
|
d[i]++, d[j]++;
|
|
|
++cnt;
|
|
|
}
|
|
|
}
|
|
|
// 读入END
|
|
|
getline(cin, s);
|
|
|
|
|
|
// 检查欧拉回路和欧拉路径
|
|
|
int odd = 0;
|
|
|
for (int i = 0; i < n; i++)
|
|
|
if (d[i] % 2) odd++;
|
|
|
|
|
|
if (odd == 0 && m == 0)
|
|
|
cout << "YES " << cnt << endl;
|
|
|
else if (odd == 2 && m != 0)
|
|
|
cout << "YES " << cnt << endl;
|
|
|
else
|
|
|
cout << "NO" << endl;
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
``` |
