题解 P6830 【[IOI 2020 Day1] Connecting Supertrees】

· · 题解

安利：IOI2020题解-洛谷博客 IOI2020题解-cnblogs

题目链接-LOJ 题目链接-洛谷

首先，如果存在 p_{i,j}=0 ,那么就分成了多个联通块，这些联通块分开做即可。

由于 p_{i,j} \leq 3 所以一个联通块当中不能出现多于一个环，否则必然会有两个点之间有 4 条路径。

没有环的情况(联通块内 p_{i,j} 均为 1 )先判掉，那么这个联通块正好有一个环。

不难发现，如果两个点 x 和 y 之间的路径需要经过多于一个环上的节点，那么 p_{x,y} 就等于 2 ,否则 p_{x,y} 为 1 , 因此如果存在 p_{x,y} = 3 那么也无解。

把所有的 p_{x,y} = 1 的 x 和 y 合并到一个联通块中，把这些块之间连成一个环， check 是否合法即可。

\Theta (n^2)

code(LOJ上通过):

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int N = 1001;
int n,cur[N],cntc,G[N][N],ans[N][N];
int p[N],l,fa[N];
inline int Find(int x){ return x == fa[x] ? x : (fa[x] = Find(fa[x])); }
inline void Merge(int x,int y){ fa[Find(x)] = Find(y); }
inline void add_edge(int x,int y){ ans[x][y] = ans[y][x] = 1; }
inline bool solve(int c){
    int i,j; bool is = 0;
    for (l = 0,i = 1; i <= n; ++i) if (cur[i] == c) p[++l] = i;
    for (i = 1; i <= l; ++i) for (j = 1; j <= l; ++j) if (G[p[i]][p[j]] != 1) is = 1;
    if (l == 1) return 1;
    if (l == 2){ if (G[p[1]][p[2]] > 1) return 0; add_edge(p[1],p[2]); return 1; }
    if (!is){ for (i = 1; i < l; ++i) add_edge(p[i],p[i+1]); return 1; }
    for (i = 1; i <= l; ++i) fa[i] = i;
    for (i = 1; i <= l; ++i) for (j = 1; j <= l; ++j) if (G[p[i]][p[j]] == 1) Merge(i,j);
    for (i = 1; i <= l; ++i) fa[i] = Find(i);
    for (i = 1; i <= l; ++i) for (j = 1; j <= l; ++j)
        if (fa[i] == fa[j] && G[p[i]][p[j]] == 2) return 0;
    for (i = 1; i <= l; ++i) for (j = 1; j <= l; ++j)
        if (fa[i] != fa[j] && G[p[i]][p[j]] == 1) return 0;
    int x = 0,lst = 0,fir,cnt = 0;
    for (i = 1; i <= l; ++i){
        x = is = 0;
        for (j = 1; j <= l; ++j) if (fa[j] == i) is = 1;
        if (!is) continue;
        ++cnt;
        for (j = 1; j <= l; ++j) if (j != i && fa[j] == i){
            if (x) add_edge(p[x],p[j]); x = j;
        }
        if (x) add_edge(p[x],p[i]);
        if (lst) add_edge(p[lst],p[i]); else fir = i; lst = i;
    }
    if (cnt < 3) return 0;
    add_edge(p[lst],p[fir]);
    return 1;
}
inline void getcur(int x,int c){
    cur[x] = c;
    for (int i = 1; i <= n; ++i) if (x != i && G[x][i] && !cur[i]) getcur(i,c);
}
inline int MAIN(){
    int i,j;
    for (i = 1; i <= n; ++i) if (!cur[i]) getcur(i,++cntc);
    for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) if (cur[i] != cur[j] && G[i][j]) return 0;
    for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) if (cur[i] == cur[j] && !G[i][j]) return 0;
    for (i = 1; i <= cntc; ++i) if (!solve(i)) return 0;
    vector<vector<int> >Ans; vector<int>ret; Ans.clear();
    for (i = 1; i <= n; ++i){
        ret.resize(n);
        for (j = 0; j < n; ++j) ret[j] = ans[i][j+1],cerr << ans[i][j+1] << ' '; cerr<<'\n';
        Ans.push_back(ret);
    }
    build(Ans);
    return 1;
}
int construct(vector<vector<int> > p){
    int i,j; n = p[0].size();
    for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) if (p[i][j] == 3) return 0;
    for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) G[i][j] = p[i-1][j-1];
    return MAIN();
}
/*
int main(){
    int n,i,j;
    cin >> n;
    vector<vector<int> >p; vector<int>q; p.clear(),q.resize(n);
    for (i = 1; i <= n; ++i){
        for (j = 0; j < n; ++j) cin >> q[j];
        p.push_back(q);

    }
    cout << construct(p) << '\n';
}
*/