首先最小拓扑序可以在拓扑排序的基础上将队列改成小根堆求出。

如何使得最小拓扑序变大？

我们在拓扑排序的某一时刻，此时当前所有入度为 $0$ 的点处于小根堆中。

对于编号最小的点，我们即将删掉它。

此时我们可以给这个点增加一条入边，使得其入度变成 $1$。

这样我们就增大了拓扑序。

所以我们可以贪心的考虑，对于每一个即将被删掉的点，我们都为它新增一条入边，这样显然是最优的。

问题在于这一条入边的起点在那里，我们发现起点为其拓扑序中的上一个即可，这样可以确保它一定出现在它当前拓扑序位置中。

那么他的拓扑序位置在哪里呢？其实可以由我们随意指定。

但需要注意的是你仍需保证其在这一时刻最小（因为实际上我们只是令它在这一时刻入度为 $0$）。

那么我们再把这样的点用大根堆存储起来，在需要的位置插入即可。

具体来说，算法流程如下：

初始化：将入度为 $0$ 的点放入小根堆中。

  • 小根堆大小大于 $1$
    • 若 $K > 0$：为当前堆顶添加入边（打标记并放入大根堆中）
    • 否则：删掉堆顶（与普通拓扑序相同）
  • 小根堆大小等于 $1$
    • 若 $K > 0$：且大根堆不为空且大根堆堆顶更大：为当前堆顶添加入边，删掉大根堆堆顶
    • 否则：删掉堆顶
  • 小根堆大小等于 $0$
    • 删掉大根堆堆顶

最后，打过标记的点和它在拓扑序列前一个点连边即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
#define P pair<int,int>
const int maxn=1e5;
int n,m,K;
vector<int> E[maxn+5];
int dg[maxn+5];
int ans[maxn+5],anst;
P ae[maxn+5];int aet;
bool flg[maxn+5];
priority_queue<int,vector<int>,greater<int>> q;
priority_queue<int,vector<int>,less<int>> p;
inline void Insert(int u){K--,flg[u]=1,p.push(u);}
inline void Delete(int u){
    ans[++anst]=u;
    if(flg[u]) ae[++aet]=P(ans[anst-1],ans[anst]);
    for(int v:E[u]) if(!(--dg[v])) q.push(v);
}
signed main(){
    int u,v;
    scanf("%d%d%d",&n,&m,&K);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        E[u].emplace_back(v);
        dg[v]++;
    }
    for(int i=1;i<=n;i++) if(!dg[i]) q.push(i);
    while(q.size()||p.size()){
        if(q.size()==0) u=p.top(),p.pop(),Delete(u);
        else if(q.size()==1){
            if(K&&p.size()&&q.top()<p.top()){
                u=q.top(),q.pop(),Insert(u);
                u=p.top(),p.pop(),Delete(u);
            }
            else u=q.top(),q.pop(),Delete(u);
        }
        else{
            if(K) u=q.top(),q.pop(),Insert(u);
            else u=q.top(),q.pop(),Delete(u);
        }
    }
    for(int i=1;i<=anst;i++) printf("%d ",ans[i]);
    putchar('\n');
    printf("%d\n",aet);
    for(int i=1;i<=aet;i++)
        printf("%d %d\n",ae[i].first,ae[i].second);
    return 0;
}