题解 [email protected]洛谷 【[IOI2020]连接擎天树】

破事水:IOI2020 结束后就想要写这题,但是 spj 当时是锅的,修好后我就秉承鸽子的良好品德一直咕到了现在。

因为 CSP2020 考的有点自闭,所以来做一道 IOI 真题放松一下。


题意简述:构造一个无向图,使得任意两个点之间路径个数与题目给出的相同。


思路:

注:因为洛谷与其他 oj(包括 IOI 官方)的评测方式不同,本题解代码以洛谷为准,在其他 oj 可能无法直接取的 AC,请额外注意。

首先,如果一个图中的一个连通块,拥有多于一个环,那么这种情况肯定不符合题意。为啥呢?画个图理解一下。

以这张图上 464\rightarrow 6 的路径为例,共有如下情况:

  1. 40164\rightarrow 0\rightarrow 1\rightarrow 6
  2. 401564\rightarrow 0\rightarrow 1\rightarrow 5\rightarrow 6
  3. 432164\rightarrow 3\rightarrow 2\rightarrow 1\rightarrow 6
  4. 4321564\rightarrow 3\rightarrow 2\rightarrow 1\rightarrow 5\rightarrow 6

因为跨过了两个环,路径条数显然多于三个。

我们得到了构造的初步方向:原图必须是一个由树或基环树组成的森林

接着找规律:

对于这棵基环树,通过手推,发现:

  1. 对于任意两个点(比如 2,42,4),它们之间的路径如果全在环外,那么它们之间有且仅有一条路径
  2. 对于任意两个点(比如 6,36,3),它们之间的路径如果至少有一条边一定在环上,那么它们之间有两条路径

换句话说,就是把所有环上的边先删掉,如果还在连通块内,就只有一条边。

可以看到,如果题目中要求 u,vu,v 之间有三条路径,此时无解

我们先 dfs 一遍求出连通块,如果连通块内存在要求有三条路径的边,就直接判掉。如果有两个点之间路径要求为零,也可以判掉。剩下的情况就分为两种:树和基环树。

对于连通块内只要求两两之间有一条路径,将其中一个点和连通块内其他所有点相连即可。对于基环树,我们先不考虑路径数为二的边,在剩下的路径数为一的边里面再次 dfs 求出环外的连通块,按照相同方式连接后,每个环外连通块取一个点,将这些点依次连城环即可。

至此我们便得到了正解。


代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;

void build(vector<vector<int> > b);

int n, ma, vis[N];
vector<int> block, edge, circle; // 分别为连通块、基环树上的树边和基环树上的环 
vector<vector<int> > graph, res;
void add(int u, int v) {res[u][v] = res[v][u] = 1;}
void dfs(int u) {
//	printf("DFS %d\n", u);
	vis[u] = 1;
	block.push_back(u);
	for(int v=0;v<n;v++) {
		ma = max(ma, graph[u][v]);
		if(!vis[v] && graph[u][v]) dfs(v);
	}
}
void dfsCircle(int u) {
	vis[u] = 2;
	edge.push_back(u);
	for(int v=0;v<n;v++) if(vis[v] == 1 && graph[u][v] == 1) dfsCircle(v);
}
int construct(vector<vector<int> > p) {
//	puts("CONSTRUCT");
	graph = p; n = p.size(); res.resize(n);
	for(int i=0;i<n;i++) res[i].resize(n);
	for(int i=0;i<n;i++) {
		if(vis[i]) continue;
		ma = 1; block.clear(); dfs(i);
//		printf("ROUND %d DFS ENDED WITH MAX=%d\n", i, ma);
		if(ma == 3) return 0;
		int sz = block.size();
		for(int j=1;j<sz;j++) {
			for(int k=0;k<j;k++) {
				if(!graph[block[j]][block[k]]) return 0;
			}
		}
		if(ma == 1) for(int j=1;j<sz;j++) add(block[0], block[j]);
		else {
			circle.clear();
			for(int _=0,j=block[_];_<sz;_++,j=block[_]) {
				if(vis[j] != 1) continue;
				edge.clear();
				dfsCircle(j);
//				puts("DFSCIRCLE ENDED");
				int sz2 = edge.size();
				for(int k=1;k<sz2;k++) {
					for(int l=0;l<k;l++) {
						if(graph[edge[k]][edge[l]] != 1) return 0;
					}
					add(edge[0], edge[k]);
				}
				circle.push_back(edge[0]);
//				printf("CIRCLE ADDED %d\n", edge[0]);
			}
			if(circle.size() <= 2) return 0;
			int sz3 = circle.size();
			for(int j=0;j<sz3;j++) add(circle[j], circle[(j+1)%sz3]);
		}
	}
	build(res);
	return 1;
}/*

void build(vector<vector<int> > b) {
	puts("BUILD");
	for(int i=0;i<b.size();i++) {
		for(int j=0;j<b[i].size();j++) printf("%d ", b[i][j]);
		puts("");
	}
}
int main() {
	vector<vector<int> > a = vector<vector<int> >
							({vector<int>({1, 1, 2, 2}), vector<int>({1, 1, 2, 2})
							, vector<int>({2, 2, 1, 2}), vector<int>({2, 2, 2, 1})});
	build(a);
	printf("CONSTRUCT ENDED WITH RETURN VALUE %d\n", construct(a));
	return 0;
}*/