[IOI2020] 连接擎天树

**这是一道交互题。** 本题仅支持 C++ 系列语言，提交时**不需要**包含 `supertrees.h` 头文件，但**需要**在程序开头包含 `vector` 头文件以及声明函数 `void build(std::vector<std::vector<int> > b);`

滨海湾花园是新加坡的一个大型自然公园。公园内有 $n$ 个塔，称之为“擎天树”。这些塔的编号为 $0$ 到 $n-1$。我们希望建立一个桥的集合（桥的数目大于等于 $0$）。每⼀座桥连接两个不同的塔，而且可以双向通行。没有两座桥连接相同的一对塔。 一条从塔 $x$ 到塔 $y$ 的路径是一个满足以下条件的塔序列（塔的数目大于等于 $1$）： - 序列的第一个元素是 $x$， - 序列的最后一个元素是 $y$， - 序列中所有元素互不相同， 序列中每两个相邻元素（塔）都是被某一座桥连接起来的。 注意根据定义，一个塔到它自己有且仅有一条路径，并且从塔 $i$ 到塔 $j$ 的不同路径的数目和从塔 $j$ 到塔 $i$ 的不同路径的数目是一样的。 负责该项设计的首席设计师希望待建造的桥梁要符合：任意给定 $0 \le i,j \le n-1$，恰好有 $p[i][j]$ 条从塔 $i$ 到塔 $j$ 的不同路径，其中 $0 \le p[i][j] \le 3$。 请构造一个桥的集合来满足设计师的要求，或判定这样的桥梁集合不可能存在。 #### 实现细节 你需要实现下面的这个函数： ```cpp int construct(std::vector<std::vector<int> > p) ``` - $p$：⼀个表示设计师要求的 $n \times n$ 数组。 - 如果这个建设方案是存在的，该函数应该恰好调用一次 `build`（见下文）来给出建设方案，然后应返回 $1$。 - 否则，该函数应该返回 $0$，并且不要调用 `build`。 - 该函数将被调用恰好一次。 函数 `build` 定义如下： ```cpp void build(std::vector<std::vector<int> > b) ``` - $b$：一个 $n \times n$ 的数组，$b[i][j]=1$ 表示有一座桥连接塔 $i$ 和塔 $j$，否则 $b[i][j]=0$。 - 注意该数组必须满足：对所有 $0 \le i,j \le n-1$，$b[i][j]=b[j][i]$；并且对所有 $0 \le i \le n-1$，$b[i][i]=0$。

#### 样例说明 #### 例 1 考虑以下调用： ```cpp construct([[1, 1, 2, 2], [1, 1, 2, 2], [2, 2, 1, 2], [2, 2, 2, 1]]) ``` 这表明从塔 $0$ 到塔 $1$ 恰好有一条路径。对于所有其他的塔对 $(x,y)(0 \le x<y \le 3)$, 恰好有两条不同的路径连接塔 $x$ 和塔 $y$。这可以通过建设 $4$ 座桥来实现：连接塔对 $(0, 1), (1, 2), (1, 3)$ 和 $(2,3)$。 为了给出这个解决方案，函数 `construct` 应该做以下调用： ```cpp build([[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]]) ```  函数应该返回 $1$。 对于这个例子，存在多种不同的建设方案来满足要求，所有这些方案都被认为是正确的。 #### 例 2 考虑以下调用： ```cpp construct([[1, 0], [0, 1]]) ``` 这表明无法在两个塔之间进行旅行。这只能通过不建设桥梁来满足。 因此，函数 `construct` 应该做以下调用： ```cpp build([[0, 0], [0, 0]]) ``` 然后，函数 `construct` 应该返回 $1$。 #### 例 3 考虑以下调用： ```cpp construct([[1, 3], [3, 1]]) ``` 这表明从塔 $0$ 到塔 $1$ 恰好有 $3$ 条路径。这些要求无法满足。因此，函数 `construct` 应该返回 $0$ 并且不要调用 `build`。 #### 约束条件 - $1\le n\le 1000$ - $p[i][i]=1$（对所有 $0 \le i \le n-1$） - $p[i][j]=p[j][i]$（对所有 $0 \le i,j \le n-1$） - $0 \le p[i][j] \le 3$（对所有 $0 \le i,j \le n-1$） #### 子任务 1. （11 分）$p[i][j]=1$（对所有 $0 \le i,j \le n-1$） 2. （10 分）$p[i][j] \in \{0,1\}$（对所有 $0 \le i,j \le n-1$） 1. （19 分）$p[i][j] \in \{0,2\}$（对所有 $i \ne j,0 \le i,j \le n-1$） 1. （35 分）$0 \le p[i][j]\le 2$（对所有 $0 \le i,j \le n-1$）并且至少有一种建设方案满足要求 1. （21 分）$0 \le p[i][j] \le 2$（对所有 $0 \le i,j \le n-1$） 1. （4 分）没有额外约束条件 #### 评测程序示例 评测程序示例以如下格式读取输入数据： 第 $1$ 行：$n$ 第 $2+i$ 行（$0 \le i \le n+1$）：$p[i][0]\ p[i][1]\ \ldots\ p[i][n]$ 评测程序示例的输出格式如下： 第 $1$ 行: `construct` 的返回值。 如果 `construct` 的返回值为 $1$，评测程序示例会额外打印： 第 $2+i$ 行（$0 \le i \le n+1$）：$b[i][0]\ b[i][1]\ \ldots\ b[i][n]$