[AGC010E] Rearranging

有点意思的构造。

首先考虑后手操作是怎样的，我们根据将不互质的数按照 在序列中的顺序，顺序靠前的向顺序靠后的连边。然后重新排序的过程就是一个拓扑排序。要使其字典序最大，我们使用优先队列即可。

接着考虑先手操作，还是在不互质的数之间进行连边，我们需要将边重新定向得到一个 DAG，使其拓扑序尽可能的小。一个简单的想法是，直接从最小的节点开始 dfs，每次走之后最小的没有被遍历的点，并且对这条边定向。最终我们得到一棵生成树，如何证明这颗生成树是最优的呢？只考虑生成树上的边最优性显然。一是返祖边，由于是要构造成DAG，所以不能存在环，于是由祖先连向后代，这样不影响原来的正确性；二是横叉边，由于两棵独立的子树内部都是最优的，意味着横叉边没有被选择是因为不够优，也不影响原来的最优性性。最终时间复杂度为 $\mathcal O(n^2\log V)$。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2e3+10,M=4e6+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n;
int a[N];
bool g[N][N],vis[N];
int tot,head[N],ver[M<<1],ne[M<<1];
int deg[N];

int gcd(int x,int y){return x?gcd(y%x,x):y;}
inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
    deg[v]++;
}
void dfs(int x)
{
    vis[x]=1;
    for(int y=1;y<=n;y++)
        if(!vis[y]&&g[x][y])
            dfs(y),add(x,y);
}
void topo()
{
    priority_queue<int>q;
    for(int i=1;i<=n;i++)if(!deg[i])q.push(i);
    while(!q.empty())
    {
        int x=q.top();
        q.pop();
        printf("%d ",a[x]);
        for(int i=head[x];i;i=ne[i])
        {
            int y=ver[i];
            if(!--deg[y])q.push(y);
        }
    }
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++)read(a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            g[i][j]=g[j][i]=(gcd(a[i],a[j])!=1);
    for(int i=1;i<=n;i++)
        if(!vis[i])
            dfs(i);
    topo();
    return 0;
}