题解 P6830 【[IOI2020]连接擎天树】

· · 题解

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

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

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

思路：

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

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

以这张图上 4\rightarrow 6 的路径为例，共有如下情况：

  1. 4\rightarrow 0\rightarrow 1\rightarrow 6
  2. 4\rightarrow 0\rightarrow 1\rightarrow 5\rightarrow 6
  3. 4\rightarrow 3\rightarrow 2\rightarrow 1\rightarrow 6
  4. 4\rightarrow 3\rightarrow 2\rightarrow 1\rightarrow 5\rightarrow 6

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

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

接着找规律：

对于这棵基环树，通过手推，发现：

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

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

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

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

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

至此我们便得到了正解。

代码：

//By: Luogu@rui_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;
}*/