agc010_e Rearranging （图论建模贪心拓扑序）

112 阅读 0 评论 74 点赞

我是靠谱客的博主危机火车，最近开发中收集的这篇文章主要介绍agc010_e Rearranging （图论建模贪心拓扑序），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

最后做法挺简单的，但确实不容易想到这么多大胆的步骤。

首先第一眼就能发现Takahashi的序列 $a$ 中如果存在 $i<j,(a[i],a[j])>1$ ，那么 $a[i]$ 和 $a[j]$ 的相对位置永远不会改变，也就相当于 $a[j]$ 永远在 $a[i]$ 后面出现。思维比较发散的人可能已经想到了拓扑——连一条边 $i->j$ ，这样就形成了一个DAG，Aoki肯定会按最大字典序来访问这个拓扑图。所以我们其实是给一个无向图（ $(a[i],a[j])>1$ 就给i和j连边）确定方向，变成有向图，使得最后最大拓扑序最小（我们称之为“最优序列”）。

先从简单的情况思考，只有一个连通块。这个时候我们一开始肯定会选择最小的那个点x开始，作为唯一一个入度为0的点。接下来的过程记为extend（x）：访问其它儿子，应该从小到大依次扩展每个儿子的势力，对每个儿子j依次进行extend（j）……这样可以保证这个联通块的最大拓扑序最小。因为从小到大extend是必须的，否则大一点的儿子要么指向小儿子，要么和小儿子没有关系。无论哪种情况，大儿子都会先被Aoki访问，这样就亏大了，所以必须让小儿子先下手为强。

有多个联通块咋办呢？我们可以感性地假设每个连通块必须满足“最优序列”才能保证整体最优，然后直接模拟Aoki的过程即可得到答案。那事实上是不是这样呢？也是容易证明的。首先找到每个连通块 $i$ 里面最小的点 $b[i]$ ，那Aoki第一步访问的点权一定不小于 $Max(b[i])$ ，所以我们让 $b[i]$ 最大的那个连通块的根节点为权值等于 $b[i]$ 的点，这样才可以得到最优答案。确定了第一个点之后，后面的证明就类似了，我们可以一步步推得每个连通块的序列就是最优序列。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#define fs first
#define sc second
#define mp make_pair
#define sf scanf
#define pf printf
#define pb push_back
#define tl(x) ((int)x.size()-1)
#define rep(i,j,k) for (i=j;i<=k;i++)
using namespace std;
const int N=1e5+5;
typedef pair<int,int> Pair;
int n,i,j,a[N],vis[N],dgr[N];
vector <int> b[N],c[N];
priority_queue <Pair> heap;
int gcd(int a,int b) {
	int c=a%b;
	while (c) {	a=b; b=c; c=a%b;}
	return b;
}
void dfs(int x)
{
	int j; vis[x]=1;
	rep(j,0,tl(b[x]))
	if (!vis[b[x][j]])
	{
		dgr[b[x][j]]=1;
		c[x].pb(b[x][j]);
		dfs(b[x][j]);
	}
}
int main()
{
	sf("%d",&n); rep(i,1,n) sf("%d",&a[i]); sort(a+1,a+1+n);
	rep(i,1,n)
		rep(j,1,n)
			if (i!=j && gcd(a[i],a[j])>1) b[i].pb(j);
	rep(i,1,n) if (!vis[i]) dfs(i);
	rep(i,1,n) if (!dgr[i]) heap.push(mp(a[i],i));
	while (!heap.empty())
	{
		i=heap.top().sc;
		heap.pop();
		pf("%d ",a[i]);
		rep(j,0,tl(c[i])) heap.push(mp(a[c[i][j]],c[i][j]));
	}
 	return 0;
}