题解 P6830 【[IOI 2020 Day1] Connecting Supertrees】
s_r_f
2020-09-19 19:15:42
安利：[IOI2020题解-洛谷博客](https://www.luogu.com.cn/blog/s-r-f/ioi2020-ti-xie) [IOI2020题解-cnblogs](https://www.cnblogs.com/s-r-f/p/13697373.html)
---
[题目链接-LOJ](https://loj.ac/problem/3365) [题目链接-洛谷](https://www.luogu.com.cn/problem/P6830)
首先，如果存在 $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上通过):
```cpp
#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';
}
*/
```