题解 AT2306 【[AGC010E] Rearranging】

· · 题解

AGC010 总题解

luogu

刚开始这题想不懂，后来和 WAPER 讨论了一下大概明白了。

对于不互质的数之间连一条边，然后形成一个竞赛图。

先手的目的是给竞赛图定向，因为不互质的数相对位置不会改变。

然后后手就是给一个不一定联通的 DAG 求一个最大的拓扑序。

先手的策略是对每个联通块 dfs，每次找到最小的没遍历的点，然后从当前点向该点连边，再忽略除了生成树以外的边，即：

bool vis[N],ir[N],e[N][N];
vector<int> adj[N];
void dfs(int u){
    vis[u]=true;
    R(v,n)if(!vis[v]&&e[u][v])
        adj[u].pb(v),dfs(v);
}
// ...
R(u,n)if(!vis[u]) ir[u]=vis[u]=true,dfs(u);

这么操作的证明大部分题解都没有讲清楚，我是这么理解的，对于一个联通块，比如这只鱼：

肯定得把 1 放在第一位，那么先把它当作根节点，假设我们已经知道要给一棵生成树定向。

然后下面有两个子树一样的东西，分别是 \{2,5,3\} 和 \{4,7\}。

两部分的定向互相没有影响，所以能做的只有让一个子树内最优。

那么当下的目的应该是让 2 在 \{3,5\} 之前。

因为这是个联通块，所以这一定是可能的。又因为只需要定向一棵生成树，所以 \{3,5\} 必须连在 2 后面（如果连在 1 后面就不能连在 2 后面了，然后 \{3,5\} 就可能被后手捣到 2 前面去）。

然后再对 \{3,5\} 这个子图内部定向，也同理，这里可以利用一个递归定向的思想。

然后最后还有一个问题：为什么要定向一个生成树。

假如我们已经定向好了一棵生成树，那么内部的边定向必然是最优的了。对于非树边，如果它是返祖边，那么它必须顺着树边方向（它不允许构成环）；否则它是某个节点下联通两个子树的边，它没被 dfs 选中说明它的定向不会更优，它只需要顺从敌人的意志即可。这样总是不会产生环的。

aclink