[图论记录]AT2306 [AGC010E] Rearranging

**题意** ： 给出一个长度为 $n$ 的序列 $a$。 玩家 A 会将序列 $a$ 任意打乱，然后玩家 B 进行操作，每次可以将两个**相邻**且**互质**的数交换。 玩家 A 希望最终序列的字典序尽量小，而玩家 B 希望最终序列的字典序尽量大，问最终序列。 $n\leq 2000$ ，时限$\texttt{2s}$。 ------------ 咋这一场 DEF 都是博弈…… 先考虑在给定序列后玩家 B 会如何操作。 对于那些不互质的数，操作后相对顺序不会改变。不难发现，这也是方案合法的充要条件。 于是，对于每一组不互质的对子 $a_i,a_j$ ，连边 $i\rightarrow j$ ，表示 $i$ 一定要在 $j$ 前面。 现在求该 $\rm DAG$ 的最大拓扑序（列）。 根据“字典拓扑原理”，用堆贪心地进行拓扑排序，每次取点权最大的点扩展即可。 然后，考虑 A 的对策。 对于每一组不互质的对子 $a_i,a_j$ ，连无向边。先手要将无向边定向，使得形成的 $\rm DAG$ 的最大拓扑序最小。 对于每个联通块，我们令权值最小的点 $t$（若有多个，则任选一个）为唯一零度点，开始向外定向。 这样能保证第一个点一定是权值最小的点。反之，若有多个零度点，则第一个点可以不是权值最小的点，更劣。 在定向时，从 $t$ 开始 $\rm dfs$ ，优先前往权值较小的儿子。 将 $\rm dfs$ 树上的边按照从上到下的顺序定向，$\rm dfs$ 的返祖边也从上到下（这些边是无用的，丢掉也行）。 若不优先前往权值较小的儿子，可能该分支与其他分支联通，造成这个儿子访问顺序必晚于某个更大的数，更劣。 若不连通，则先走谁没关系。“优先前往权值较小的儿子”这一策略能保证每个联通分量先被遍历到可能的最小点，故是最优的， 确定了图之后，跑 B 的贪心即可。 复杂度 $O(n^2\log a)$。 ```cpp #include<algorithm> #include<cstdio> #include<vector> #include<queue> #define Pr pair<int,int> #define fir first #define sec second #define mp make_pair #define pb push_back #define MaxN 2050 using namespace std; int gcd(int a,int b) {return !b ? a : gcd(b,a%b);} vector<int> g[MaxN],g2[MaxN]; int rt,a[MaxN],d[MaxN],vis[MaxN]; void adl(int u,int v) {g2[u].pb(v);d[v]++;} void dfs1(int u) { if (a[u]<a[rt])rt=u; vis[u]=1; for (int i=0;i<g[u].size();i++) if (!vis[g[u][i]])dfs1(g[u][i]); } void dfs2(int u) { vis[u]=2; for (int i=0;i<g[u].size();i++) if (vis[g[u][i]]!=2){ adl(u,g[u][i]); dfs2(g[u][i]); } } int n,ans[MaxN],tn; priority_queue<Pr> q; bool cmp(int A,int B){return a[A]<a[B];} int main() { scanf("%d",&n); for (int i=1;i<=n;i++)scanf("%d",&a[i]); a[0]=100000001; for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) if (gcd(a[i],a[j])>1) {g[i].pb(j);g[j].pb(i);} for (int i=1;i<=n;i++) sort(g[i].begin(),g[i].end(),cmp); for (int i=1;i<=n;i++) if (!vis[i]){ rt=0;dfs1(i); dfs2(rt); } for (int i=1;i<=n;i++) if (!d[i])q.push(mp(a[i],i)); while(!q.empty()){ Pr now=q.top();q.pop(); ans[++tn]=now.fir; int u=now.sec; for (int i=0;i<g2[u].size();i++) if (!--d[g2[u][i]])q.push(mp(a[g2[u][i]],g2[u][i])); } for (int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; } ```