【2023武汉集训模拟赛7】灭国 做题记录

有个 $n$ 个点 $m$ 条边的 DAG，你要加不超过 $k$ 条边，使得加完之后还是一个 DAG，并且 这个 DAG 的字典序最小拓扑序字典序最大。

$1\le n,m,k\le 10^5$。

求出给定 DAG 的字典序最小拓扑序显然只需要把拓扑排序的队列换成小根堆，那么考虑贪心。

称原图拓扑排序所用的小根堆为 $q$，那么某一时刻若 $q$ 中有 $>1$ 个点且加边的次数还没用完则可以通过加边来延后 $q$ 中最小的点被删除的时间。设这个最小的点是 $u$，那么把 $u$ 从 $q$ 中删除，加入到一个大根堆 $q2$ 中。注意到这样操作相当于是加了一条指向 $u$ 的边。

当 $q$ 中没有元素且 $q2$ 中还有元素时，为了保证图还是 DAG 我们就不得不让 $q2$ 中的某个点被删掉了，显然把 $q2$ 中最大的点删掉是最优的。设这个点是 $u$，那么指向 $u$ 的边一定是由当前拓扑序中最后一个点 $v$ 连过来的，那么把边 $v\to u$ 加入答案序列中即可。

最后有一个细节，第一层一定要留一个点在 $q$ 中，因为无法加边。以后的每一层，$q$ 中还剩下一个点 $u$ 时，若 $q2$ 也非空，且最大的点为 $v$，并且还能加边，那么：

• $u>v$ 此时延后 $u$ 被删除的时间是没有意义的，因为加入 $q2$ 后它马上就会从 $q2$ 中取出，所以直接顺其自然；
• $u<v$ 此时延后 $u$ 被删除的时间显然是更优的，那么把 $u$ 从 $q$ 中删除，加入 $q2$；

代码如下：

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <queue>

using namespace std;

const int S=100005;

int n,m,k;
set<pair<int,int>> st;
vector<int> g[S];
int ind[S];
int cnt,a[S];
vector<pair<int,int>> ans;

int main()
{
	freopen("destroy.in","r",stdin);
	freopen("destroy.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(st.count(make_pair(x,y))) continue;
		st.insert(make_pair(x,y));
		g[x].push_back(y);
		ind[y]++;
	}
	priority_queue<int> q,q2;
	for(int i=1;i<=n;i++) if(ind[i]==0) q.push(-i);
	while(k>0&&q.size()>1) q2.push(-q.top()),q.pop(),k--;
	while(!q.empty()||!q2.empty())
	{
		int u;
		if(!q.empty()) u=-q.top(),q.pop();
		else
		{
			u=q2.top();
			q2.pop();
			ans.push_back(make_pair(a[cnt],u));
		}
		a[++cnt]=u;
		for(int v:g[u])
		{
			if(--ind[v]==0) q.push(-v);
		}
		while(k>0&&q.size()>1) q2.push(-q.top()),q.pop(),k--;
		if(k>0&&!q.empty()&&!q2.empty()&&-q.top()<q2.top())
		{
			q2.push(-q.top()),q.pop();
			k--;
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	printf("\n");
	printf("%d\n",ans.size());
	for(pair<int,int> u:ans)
	{
		printf("%d %d\n",u.first,u.second);
	}
	return 0;
}