Berland and the Shortest Paths

题意翻译

## 题目描述 Berland 有 $n$ 座城市。一些城市通过道路连接。所有道路都是双向的。每条道路连接两个不同的城市。一对城市之间至多有一条道路。城市从 $1$ 到 $n$ 编号。 众所周知，从首都（编号为 $1$ 的城市），您可以沿着道路移动并到达任何其他城市。 Berland 的总统计划改善该国的道路网。预算足以修复 $n-1$ 道路。总统计划选择 $n-1$ 条道路，要求： - 从首都出发沿着这 $n-1$ 条道路走可以到达其他所有的城市。 - 如果 $d_i$ 表示首都到 $i$ 号城市所需经过的路的条数，沿着选择的 n-1 条路走所得的 $d_1$+$d_2$+・・・+$d_n$ 应是最小的。 换句话说，这 $n-1$ 条道路的应该保持国家的连通性，并且使从城市 $1$ 到所有城市的距离的总和最小（你只能使用被选择的 $n-1$ 道路）。 总统命令有关部门准备 $k$ 个可能的选择，选择的 $n-1$ 条道路同时满足以上两个条件。 编写一个程序，找到 $k$ 种可能的方法来选择道路进行维修。如果少于 $k$ 种选法，则程序应输出所有可能的有效方式来选择道路。 ## 输入输出格式 ### 输入格式： 输入的第一行包含整数 $n,m,k.$ $(2 \leq$ $ n \le $ $2 \cdot $ $10^5,$ $n-1$ $\leq$ $m \leq$ $2$ $\cdot $ $10^5,$ $1 \leq$ $k$ $\leq$ $2 \cdot $ $10^5$ $),$ $n$ 是这个国家的城市数，$m$ 是道路数，并且 $k$ 是选 $n-1$ 条道路修复的方案数。 数据保证 $m \cdot k \leq 10^6.$ 接下来的 $m$ 行描述路的情况，每条路的描述占一行。每行包括两个整数 $a_i,b_i (1 \leq a_i,b_i\leq n,a_i \neq b_i)$—— 第 $i$ 条道路连接的两座城市的编号。一对城市最多有一条路连接。给定的路足以使你从首都出发到达任意城市。 ### 输出格式： 输出 $t (1 \leq t \leq k)$— 可选择的方案数量。记得你需要找到 $k$ 种不同的可行解，如果解的个数少于 $k$ 种，你需要输出所有可行解。 在接下来的 $t$ 行中，输出道路选择情况，一种一行。用 $m$ 个字符的字符串输出选择情况，其中，第 $j$ 个字符表示第 $j$ 条道路是否被选中，若是则用 $1$ 表示，若不是则用 $0$ 表示。路应该按照它们输入的顺序编号。各种选择情况的输出没有指定顺序。$t$ 行的所有输出应该不同。 因为题目保证 $m \cdot k\leq 10^6,t$ 行输出的总长不超过 $10^6.$ 如果有很多组答案，任意输出它们中的一些即可。

题目描述

There are $ n $ cities in Berland. Some pairs of cities are connected by roads. All roads are bidirectional. Each road connects two different cities. There is at most one road between a pair of cities. The cities are numbered from $ 1 $ to $ n $ . It is known that, from the capital (the city with the number $ 1 $ ), you can reach any other city by moving along the roads. The President of Berland plans to improve the country's road network. The budget is enough to repair exactly $ n-1 $ roads. The President plans to choose a set of $ n-1 $ roads such that: - it is possible to travel from the capital to any other city along the $ n-1 $ chosen roads, - if $ d_i $ is the number of roads needed to travel from the capital to city $ i $ , moving only along the $ n-1 $ chosen roads, then $ d_1 + d_2 + \dots + d_n $ is minimized (i.e. as minimal as possible). In other words, the set of $ n-1 $ roads should preserve the connectivity of the country, and the sum of distances from city $ 1 $ to all cities should be minimized (where you can only use the $ n-1 $ chosen roads). The president instructed the ministry to prepare $ k $ possible options to choose $ n-1 $ roads so that both conditions above are met. Write a program that will find $ k $ possible ways to choose roads for repair. If there are fewer than $ k $ ways, then the program should output all possible valid ways to choose roads.

输入输出格式

输入格式

The first line of the input contains integers $ n $ , $ m $ and $ k $ ( $ 2 \le n \le 2\cdot10^5, n-1 \le m \le 2\cdot10^5, 1 \le k \le 2\cdot10^5 $ ), where $ n $ is the number of cities in the country, $ m $ is the number of roads and $ k $ is the number of options to choose a set of roads for repair. It is guaranteed that $ m \cdot k \le 10^6 $ . The following $ m $ lines describe the roads, one road per line. Each line contains two integers $ a_i $ , $ b_i $ ( $ 1 \le a_i, b_i \le n $ , $ a_i \ne b_i $ ) — the numbers of the cities that the $ i $ -th road connects. There is at most one road between a pair of cities. The given set of roads is such that you can reach any city from the capital.

输出格式

Print $ t $ ( $ 1 \le t \le k $ ) — the number of ways to choose a set of roads for repair. Recall that you need to find $ k $ different options; if there are fewer than $ k $ of them, then you need to find all possible different valid options. In the following $ t $ lines, print the options, one per line. Print an option as a string of $ m $ characters where the $ j $ -th character is equal to '1' if the $ j $ -th road is included in the option, and is equal to '0' if the road is not included. The roads should be numbered according to their order in the input. The options can be printed in any order. All the $ t $ lines should be different. Since it is guaranteed that $ m \cdot k \le 10^6 $ , the total length of all the $ t $ lines will not exceed $ 10^6 $ . If there are several answers, output any of them.

输入输出样例

输入样例 #1

4 4 3
1 2
2 3
1 4
4 3

输出样例 #1

2
1110
1011

输入样例 #2

4 6 3
1 2
2 3
1 4
4 3
2 4
1 3

输出样例 #2

1
101001

输入样例 #3

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

输出样例 #3

2
111100
110110

题意翻译

## 题目描述 Berland 有 $n$ 座城市。一些城市通过道路连接。所有道路都是双向的。每条道路连接两个不同的城市。一对城市之间至多有一条道路。城市从 $1$ 到 $n$ 编号。 众所周知，从首都（编号为 $1$ 的城市），您可以沿着道路移动并到达任何其他城市。 Berland 的总统计划改善该国的道路网。预算足以修复 $n-1$ 道路。总统计划选择 $n-1$ 条道路，要求： - 从首都出发沿着这 $n-1$ 条道路走可以到达其他所有的城市。 - 如果 $d_i$ 表示首都到 $i$ 号城市所需经过的路的条数，沿着选择的 n-1 条路走所得的 $d_1$+$d_2$+・・・+$d_n$ 应是最小的。 换句话说，这 $n-1$ 条道路的应该保持国家的连通性，并且使从城市 $1$ 到所有城市的距离的总和最小（你只能使用被选择的 $n-1$ 道路）。 总统命令有关部门准备 $k$ 个可能的选择，选择的 $n-1$ 条道路同时满足以上两个条件。 编写一个程序，找到 $k$ 种可能的方法来选择道路进行维修。如果少于 $k$ 种选法，则程序应输出所有可能的有效方式来选择道路。 ## 输入输出格式 ### 输入格式： 输入的第一行包含整数 $n,m,k.$ $(2 \leq$ $ n \le $ $2 \cdot $ $10^5,$ $n-1$ $\leq$ $m \leq$ $2$ $\cdot $ $10^5,$ $1 \leq$ $k$ $\leq$ $2 \cdot $ $10^5$ $),$ $n$ 是这个国家的城市数，$m$ 是道路数，并且 $k$ 是选 $n-1$ 条道路修复的方案数。 数据保证 $m \cdot k \leq 10^6.$ 接下来的 $m$ 行描述路的情况，每条路的描述占一行。每行包括两个整数 $a_i,b_i (1 \leq a_i,b_i\leq n,a_i \neq b_i)$—— 第 $i$ 条道路连接的两座城市的编号。一对城市最多有一条路连接。给定的路足以使你从首都出发到达任意城市。 ### 输出格式： 输出 $t (1 \leq t \leq k)$— 可选择的方案数量。记得你需要找到 $k$ 种不同的可行解，如果解的个数少于 $k$ 种，你需要输出所有可行解。 在接下来的 $t$ 行中，输出道路选择情况，一种一行。用 $m$ 个字符的字符串输出选择情况，其中，第 $j$ 个字符表示第 $j$ 条道路是否被选中，若是则用 $1$ 表示，若不是则用 $0$ 表示。路应该按照它们输入的顺序编号。各种选择情况的输出没有指定顺序。$t$ 行的所有输出应该不同。 因为题目保证 $m \cdot k\leq 10^6,t$ 行输出的总长不超过 $10^6.$ 如果有很多组答案，任意输出它们中的一些即可。