【AtCoder2306】Rearranging（拓扑）

题意

黑板上有n个数，A首先按照自己的意愿将n个数重新排列(可以是原来的顺序),然后让B进行如下操作:
选择一对相邻且互质的数,交换它们的位置.(这个操作B可以进行无数次.)
A想要这个序列的字典序尽可能小,而B想要这个序列的字典序尽可能大。
两人都采取最优策略的情况下,最后形成的序列是什么样子的.

题解

发现不互质的数，只要在一开始A放好后，顺序就固定下来，无法改变。
为了使得字典序最小，我们对每个数u，向最小的没被访问过的与它不互质的数v连一条边，表示u保证在v之前，为了使得字典序最小，必须保证每个点的入度为1，如图

如果这样连边，可以构造出{3,2,4,6}

显然没有这样连边更优，保证了2一定在最前面

实现时，预处理处每个数与哪些数不互质，然后dfs，对每个数优先向小的数连边，建成树状的有向图。然后利用优先队列求字典序最大的拓扑序。

代码

#include<cstdio> #include<cstdlib> #include<vector> #include<queue> #include<algorithm> using namespace std; const int MAXN=2005; int gcd(int a,int b) {
      if(b==0) return a; return gcd(b,a%b); } int n,A[MAXN]; bool vis[MAXN]; vector<int> adj[MAXN],adj2[MAXN]; int deg[MAXN],ans[MAXN]; priority_queue<int> Q; void dfs(int u) {
      vis[u]=true; for(int i=0;i<(int)adj[u].size();i++) {
      int v=adj[u][i]; if(vis[v]) continue; adj2[u].push_back(v); deg[v]++; dfs(v); } } int main() {
      scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&A[i]); sort(A+1,A+n+1); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j&&gcd(A[i],A[j])>1) adj[i].push_back(j); for(int i=1;i<=n;i++) if(!vis[i]) dfs(i); for(int i=1;i<=n;i++) if(deg[i]==0) Q.push(i); int it=0; while(!Q.empty()) {
      int u=Q.top(); ans[++it]=A[u]; Q.pop(); for(int i=0;i<(int)adj2[u].size();i++) {
      int v=adj2[u][i]; deg[v]--; if(deg[v]==0) Q.push(v); } } for(int i=1;i<n;i++) printf("%d ",ans[i]); printf("%d\n",ans[n]); return 0; }