problem

洛谷鏈接

題意：給定 $m$ 條形如 $(u,v)$ 的限制，要求 $a_u,a_v$ 的相對大小關系與 $b_u,b_v$ 相同。

且盡可能減少 $a_i=b_i$ 的數量，輸出 $a,b$ 兩個排列。

solution

我們考慮將每條 $(u,v)$ 限制轉化成圖 $G$ 中的一條邊。

如果某個點 $i$ 的邊數 $=n?1$，則一定有 $a_i=b_i$。（$n$ 為當前剩余點的數量）

邊數等于點數減一，這說明點 $i$ 與其它所有點都有一定的要求，假設要求 $b_i>b_k$ 的 $k$ 有 $x$ 個，則 $a_i>a_k^{\prime }$ 的 $k^{\prime }$ 也等于 $x$。

這種確定的點直接按死不參與后面的討論了。

那么到這里就剩下了一堆邊數 $<n?1$ 的點了。

反轉邊的定義，$\bar{G}=E?G$，如果 $(u,v)$ 在 $\bar{G}$ 為一條邊當且僅當 $(u,v)$ 原來是沒有限制的。

這些點都是沒有滿邊的，所以一定會跟至少一個其它點連邊的。

$\bar{G}$ 形成的是一個生成樹森林，沒有必要多連邊形成圖，獨立是傳遞的，所以 $\bar{G}$ 是多樣的。

現在連邊的兩個點之間的選擇是互不干涉的。

考慮一個特殊的情況——兩層的菊花圖。有一個非常簡單的構造。

假設菊花圖的根為 $u$，所有葉子依次為 $v_1,v_2,...,v_x$。

對于 $a$ 序列，$a_u=l,a_{v_1}=l+1,...,a_{v_{x?1}}=l+x?1,a_{v_x}=l+x$。

對于 $b$ 序列，$b_u=l+1,b_{v_1}=l+2,...,b_{v_{x?1}}=l+x,b_{x_v}=l$。

用同樣的數字區間 $[l,l+x]$ 填寫了 $a,b$ 同樣的點集，且打了個等差 $1$。

這樣子，內部反正是沒有限制，不用管數字間的大小，也沒有產生多余的 $a_i=b_i$ 情況數。

而與外部部分，因為都是用的連續段數字，相對關系也是滿足的。

例如有個點 $t$ 與內部點有相對大小關系的限制，內部用的是 $[l,l+x]$ ，$t$ 所在點無論是 $[l^{\prime },l)/(l+x,r^{\prime }]$，$a,b$ 都是一致的。要么都小于最小值，要么都大于最大值。

將 $\bar{G}$ 中一些邊斷掉是不會出錯的（因為這反而相當于外加了一些限制）。

所以，我們可以就將 $\bar{G}$ 直接斷成若干個兩層菊花圖。

換言之，最后的答案最少個數可以通過調整構造變成最開始確定的點的數量。

有很多種裂成不同菊花圖的方法，下面是官方做法：

枚舉未分配的節點 $u$。

• 如果 $u$ 有臨邊點 $v$ 未分配，將 $u$ 和所有未分配的 $v$ 一起構成一個新的菊花圖，并以 $u$ 為根。

• 否則，說明 $u$ 的所有鄰居均已有過分配的菊花圖。隨便選一個鄰居 $v$。

  • 如果 $v$ 所在的菊花圖至少有 $3$ 個點，那么就可以把 $v$ 割裂出來，使得 $u,v$ 成為新的菊花圖。

    注意：$v$ 此時不可能是其所在菊花圖的根，如果是那么 $u$ 早就隸屬與 $v$ 為根的那個菊花圖了。

  • 否則，說明 $v$ 所在的菊花圖只有兩個點，將 $u$ 加入那個菊花圖，并將那個菊花圖轉變為以 $v$ 為根即可。

$\bar{G}$ 中可存在的邊很多，$n^2$ 級別的，但不一定是全都必須出現的。怎么快速求出想要的生成樹？

用兩個 set 維護已出現在 $\bar{G}$ 中的點和還未出現的點，在 dfs-tree 的時候順便加邊構出生成樹的邊。

時間復雜度：$O((n+m)\log n)$。

code

#include <bits/stdc++.h> using namespace std; #define maxn 500005 set < pair < int, int > > graph; set < int > id, G[maxn], R[maxn]; int id1[maxn], id2[maxn], deg[maxn];void dfs( int u ) {id.erase( u );int v = 0;while( 1 ) {auto it = id.upper_bound( v );if( it == id.end() ) break;v = *it;if( G[u].find( v ) != G[u].end() ) continue;R[u].insert( v );R[v].insert( u );dfs( v );} }int main() {int T, n, m;scanf( "%d", &T );while( T -- ) {scanf( "%d %d", &n, &m );for( int i = 1;i <= n;i ++ ) G[i].clear(), R[i].clear();id.clear(); for( int i = 1;i <= n;i ++ ) id.insert( i );for( int i = 1, u, v;i <= m;i ++ ) {scanf( "%d %d", &u, &v );G[u].insert( v );G[v].insert( u );}while( id.size() ) dfs( * id.begin() );int num = n;for( int i = 1;i <= n;i ++ ) {deg[i] = R[i].size();if( deg[i] ) graph.insert( make_pair( deg[i], i ) );else id1[i] = id2[i] = num --;}int l = 0, r = 0, u;while( graph.size() ) {u = graph.begin() -> second;u = *R[u].begin();graph.erase( make_pair( deg[u], u ) );vector < int > scc;for( int v : R[u] ) {graph.erase( make_pair( deg[v], v ) );if( deg[v] == 1 ) scc.push_back( v );else graph.insert( make_pair( -- deg[v], v ) ), R[v].erase( u );}id1[u] = ++ l; for( int i : scc ) id1[i] = ++ l, id2[i] = ++ r; id2[u] = ++ r;}for( int i = 1;i <= n;i ++ ) printf( "%d ", id1[i] ); puts("");for( int i = 1;i <= n;i ++ ) printf( "%d ", id2[i] ); puts("");}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的CodeForces1477D Nezzar and Hidden Permutations（构造+调整+菊花图）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。