G - Graph Gym - 100801G（拓扑排序+优先队列）

本文主要是介绍G - Graph Gym - 100801G（拓扑排序+优先队列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
一个有向无环图，由1~n的点组成。
要求加至多k条边使得拓扑排序得到的最小字典序最大

思路：
首先确定，通过加边改变拓扑序，只是对于当前可选的点如$x1,x2,x3$，改变$x1,x2,x3$的输出相对顺序。而对于$a->b->c->d$，怎么连边都不能让$d$先输出。

假设一个超级源点0，0连接了所有点。
因为题意求的是最小字典序，那么将队列换成小根堆$p$

第一轮入堆的为0。
输出的点为0.
第二轮入堆的点为$x1,x2,x3$，且$x1<x2<x3$。
那么最小字典序，肯定要先出点$x1$。如果此时我们还能多加边，我们肯定希望能通过加边使得$x1$这个点后出，只需要用上一次输出的点连上$x1$即可。于是设置一个大根堆$q$，将$x1$放在$q$中，意思是等下考虑。

$x2$也是同样的操作，放入$q$中，等下考虑。（假设$k$足够）

但到了$x3$，此时$p$中只有这一个点，那么如果此时不输出这个点而放到$q$中等下考虑，那么上一次的点只剩下了0，连上就成环了。而且此时$x3$大于$q$中待选的所有点，现在输出就是最优的，无需继续等待了。

之后也是如此，我们有小根堆$p$代表当前的可选点，大根堆$q$代表通过加边改变顺序的点。

如果还能加边，那么就将$p$中的点尽可能放到$q$中，知道$p$中只剩下一个点，且这个点大于$q$中所有点，此时这个点放入$q$中就会成环。

之后如果$p$中有点，就输出$p$中的点。
$q$中有点，就输出$q$中的点，并将之前输出的点连一条边在当前输出的点上。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;const int maxn = 2e5 + 7;priority_queue<int,vector<int>,greater<int>>p; //小根堆
priority_queue<int>q; //大根堆
vector<int>a;
vector<pair<int,int>>b;
int n,m,k;
int head[maxn],nex[maxn],to[maxn],tot;
int deg[maxn];void add(int x,int y) {to[++tot] = y;nex[tot] = head[x];head[x] = tot;
}void topo() {int pre = 0,now = 0;for(int i = 1;i <= n;i++) {if(deg[i] == 0) p.push(i);}while(p.size() || q.size()) {while(p.size() && k) {int x = 0,y = 0;x = p.top();if(q.size()) y = q.top();if(x > y && p.size() == 1) break; //如果不加这个条件，那么pre可能为0或者会成环。因为当小根堆只有一个点并且比大根堆点都大的时候，下一次输出的只能是这个点，那么为了使这个点延后输出，我们只能用这个点连父亲，这就成环了。q.push(x);p.pop();k--;}if(p.size()) {now = p.top();p.pop();}else {now = q.top();q.pop();b.push_back({pre,now});}a.push_back(now);for(int i = head[now];i;i = nex[i]) {int v = to[i];deg[v]--;if(deg[v] == 0) {p.push(v);}}pre = now;}
}int main() {freopen("graph.in","r",stdin);freopen("graph.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);add(x,y);deg[y]++;}topo();for(int i = 0;i < a.size();i++) {printf("%d ",a[i]);}printf("\n%d\n",b.size());for(int i = 0;i < b.size();i++) {printf("%d %d\n",b[i].first,b[i].second);}return 0;
}

这篇关于G - Graph Gym - 100801G（拓扑排序+优先队列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---