P9803 题解

比较弱智的构造方法。

题意

给出一个有向图，构造一个长方体空间，其中有

n

个有标号的特殊空格，当且仅当图上存在路径

i\to j

，空间中

i

可以到达

j

。

Part 0

所以考虑到一个强连通分量中的的点相当于一整个点，进行缩点。得到一个 DAG。然后使用 floyd 求传递闭包得出 SCC 之间的可达性。

Part 1

考虑样例如何构造：

可以通过给图分层构造阶梯型，每级之间高度相差

2

解决。但是对于复杂的 DAG 就较为困难。

Part 2

注意到障碍可以悬空，所以把每一层填满，然后边通过在平面上扣洞解决：

由于是 DAG，所以满足条件的方案一定存在。

Part 3

最终构造方案：

$3 \times 2n \times 2\operatorname{cnt}(\operatorname{SCC})$ 的长方体。
对于每一组（两个）面，上方的面维护点之间的可达性，如：
PLAIN
```
##1
..2
##.
...
```
表示 $1$ 与 $2$ 和编号为 $2$ 的强连通分量之间有边。（二者所在强连通分量编号为 $1$ ）

而下方的面维护每一个洞掉到哪层。
输出答案。

CODE

CPP

# include <bits/stdc++.h>
# define rep(i, a, b) for(int i = (a);i <= (b);i ++)
# define lop(i, a, b) for(int i = (a);i <  (b);i ++)
# define dwn(i, a, b) for(int i = (a);i >= (b);i --)
# define int64 long long
# define ___main signed main()
# define f64 double
# define f32 float
# define f128 long double
# define int128 __int128
# define i128 ((__int128)1)
# define ret return
# define inl inline
# define reg register
# define fn void
# define elif else if
# define pb push_back
# define pp pop_back
using std::cout;
using std::cin;
const int N=20;
int n,m,f[N],g[N][N],col[N],mp[N][N];
std::vector<int>p[N];
int find(int x){
    return(f[x]==x?x:f[x]=find(f[x]));
}
int TopNum[N], In[N], Rnk[N];
//bool b2;
char S[20][4];
signed main(){
   cin >> n;
   rep(i, 1, n)
      rep(j, 1, n)
         cin >> g[i][j];

   rep(k, 1, n)
      for (int i = 1; i <= n; i++)
         for (int j = 1; j <= n; j++)
            if (i != j) g[i][j] |= g[i][k] & g[k][j];

   for (int i = 1; i <= n; i++) f[i] = i;
   for (int i = 1; i <= n; i++)
      for (int j = 1; j < i; j++)
         if (g[i][j] && g[j][i]) {
            int u = find(i), v = find(j);
            if (u ^ v) f[u] = v;
         }

   for (int i = 1; i <= n; i++) {
      if (find(i) == i) col[i] = ++m;
      p[col[f[i]]].push_back(i);
   }

   for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
         if (g[i][j] && f[i] ^ f[j])
            mp[col[f[i]]][col[f[j]]] = 1;

   std::queue<int> q;
   for (int i = 1; i <= m; i++)
      for (int j = 1; j <= m; j++)
         In[j] += mp[i][j];

   for (int i = 1; i <= m; i++)
      if (!In[i]) q.push(i);

   while (!q.empty()) {
      int u = q.front(); q.pop();
      TopNum[u] = ++TopNum[0];
      Rnk[TopNum[u]] = u;
      for (int v = 1; v <= m; v++)
         if (mp[u][v]) {
            In[v]--;
            if (!In[v]) q.push(v);
         }
   }
   cout << 3 << " " << n * 2 << " " << TopNum[0] * 2 << "\n";
   rep(i, 1, TopNum[0]){//int i = Rnk[I];
      memset(S, '.', sizeof S);
      rep(j, 1, n * 2) S[j][3] = 0;
      rep(j, 1, TopNum[0]) {
         S[j * 2 - 1][0] = S[j * 2 - 1][1] = '#';
         S[j * 2][0] = '.';
         if(mp[Rnk[i]][Rnk[j]] || i == j) S[j * 2][1] = '.';
         else S[j * 2][1] = '#';
      }
      ///cout << Rnk[i] << " ";
      rep(j, 1, p[Rnk[i]].size()) {
         //cout << j << " ";
         S[j][2] = p[Rnk[i]][j - 1] + '0';
      }//cout << "\n";
      rep(j, p[Rnk[i]].size() + 1, n * 2)
         S[j][2] = '.';
      rep(i, 1, n * 2) cout << S[i] << "\n";
      memset(S, '#', sizeof S);
      rep(j, 1, n * 2) S[j][3] = 0;
      rep(j, 1, TopNum[0]) if(i == j) S[j * 2][0] = '#'; else S[j * 2][0] = '.';
      rep(i, 1, n * 2) cout << S[i] << "\n";
   }
   return 0;
}

文章操作

题意