P9803 题解

HDS_Acenaphthylene · 2025-10-31 11:29:23 · 题解

比较弱智的构造方法。

题意

给出一个有向图，构造一个长方体空间，其中有 n 个有标号的特殊空格，当且仅当图上存在路径 i\to j，空间中 i 可以到达 j。

Part 0

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

Part 1

考虑样例 如何构造：

可以通过给图分层构造阶梯型，每级之间高度相差 2 解决。但是对于复杂的 DAG 就较为困难。

Part 2

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

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

Part 3

最终构造方案：

2. 对于每一组（两个）面，上方的面维护点之间的可达性，如：

   ##1
   ..2
   ##.
   ...

   表示 1 与 2 和编号为 2 的强连通分量之间有边。（二者所在强连通分量编号为 1）

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

3. 输出答案。

   CODE

   # 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;
   }