[AdditionalFile5349.zip](file://AdditionalFile5349.zip?type=additional_file)

P3475 [POI 2008] POD-Subdivision of Kingdom

题目背景

English Edition

题目描述

给出一张有 $n$ 个点 $m$ 条边的无向图，你需要求出一组合法的方案，使得图被划分为点数均为 $\frac n2$ 的两个集合，且两个端点在不同集合中的边数最少。

输入格式

第一行两个整数 $n,m$。

之后 $m$ 行，每行两个整数 $a, b$，表示在 $a$ 与 $b$ 之间有一条边。

输出格式

一行 $\frac n2$ 个整数，表示在你求出的方案中的一个集合的所有点，由编号从小到大排序。

输入输出样例 #1

输入 #1

6 8
1 2
1 6
2 3
2 5
2 6
3 4
4 5
5 6

输出 #1

1 2 6

说明/提示

对于 $100\%$ 的数据，$1\le n\le 26$，$1\le a,b\le n$，且 $n$ 为偶数。保证没有重边。

#5349. 「POI2008 R3」王国划分 Subdivision of Kingdom

标签: 传统 | 时间限制: 2500 ms | 内存限制: 32 MiB |

题目描述

题目译自 XV OI Olimpiada Informatyczna – III etap Podział Królestwa

拜托西亚国王 Bajtazar 决定退休。他有两个儿子，但他无法决定由哪个儿子继任王位。因此，他决定将王国一分为二，让两个儿子分别统治一半的领土。

在王国划分后，必须在连接两半王国的道路上建造哨所。由于建造哨所需要成本，连接两半王国的道路数量应尽可能少。

拜托西亚由偶数个城市组成，这些城市通过道路相连。划分后，每一半王国应包含一半数量的城市。每条道路连接两个城市。道路之间不在城市以外的地方相交或交叉，但可以有立交桥或隧道。任意两个城市之间最多有一条直接连接的道路。

在划分王国时，哪些城市属于哪一半非常重要。你可以假设城市以外的区域可以划分得当，使得连接同一半王国内城市的道路不会跨越边界。而每条连接不同半王国城市的道路上都需要建造一个哨所。

编写一个程序，完成以下功能：

• 从标准输入读取城市及连接它们的道路的描述，
• 确定一种将王国划分为两半的方案，使每一半包含相同数量的城市，且连接不同半王国的道路数量最少，
• 将结果输出到标准输出。

如果存在多个符合条件的划分方案，你的程序可以输出其中任意一个。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $m$，用单个空格分隔，分别表示城市数量和连接它们的道路数量，$2 \leq n \leq 26$，$n$ 为偶数，$0 \leq m \leq \frac{n \cdot (n-1)}{2}$。城市编号从 $1$ 到 $n$。

接下来的 $m$ 行，每行包含两个整数，用单个空格分隔。第 $(i+1)$ 行（$i=1,2,\ldots,m$）包含数字 $u_{i}$ 和 $v_{i}$，$1 \leq u_{i} < v_{i} \leq n$，表示连接城市 $u_{i}$ 和 $v_{i}$ 的道路。

输出格式

输出一行，包含 $\frac{n}{2}$ 个整数，用单个空格分隔。这些数字应为属于包含城市 $1$ 那一半王国的城市编号，按升序排列。

样例

输入

6 8
1 2
1 6
2 3
2 5
2 6
3 4
4 5
5 6

输出

1 2 6

图中用虚线标出了最优划分方案，需要建造 $3$ 个哨所。