[图论记录]P7054 [NWRRC2015]Graph
command_block
2021-10-20 08:34:29
**题意** ： 给定一张 $n$ 点 $m$ 条边的有向无环图，你可以至多添加 $k$ 条有向边，使得这仍然是一个有向无环图，使得字典序最小的拓扑序的字典序尽量大。
求出这个最大的最小拓扑序，并构造一种加边方案。
$n,m,k\leq 10^5$ ，时限$\texttt{2s}$。
------------
- **性质** ： 记最终的拓扑序为 $P$ ，则加入的边一定可以都形如 $P_i\rightarrow P_{i+1}$。
**证明** ： 将每个加入的弱连通块换成一条链，显然不会增多边数，且不会减弱限制。
根据这条性质，如果我们得到了 $P$ ，那么只需要知道那些点有（新）入度，就可以得到需要连的边。
下面考虑构造：字典序贪心。
确定某一位拓扑序 $P_i$ 时，考虑目前所有 $0$ 入度点中最小的 $u$。
- ① 若 $u$ 为唯一的 $0$ 入度点或 $k=0$，那么我们不得不将 $u$ 弹出（并删除其出边），作为这一位拓扑序。
- ② 若 $u$ 并不是唯一的 $0$ 入度点且 $k>0$，那么我们可以给 $u$ 加一条入边。
我们暂不考虑入边的起点是谁。
如上流程有个问题，将 $u$ 弹出并删除其出边时，我们不能确定 $u$ 是否是某个新边的起点。
但我们不能从“起点”出发考虑，那样太麻烦，转而从“终点”出发考虑。
我们引入“次 $0$ 入度点”的概念，指这些点原本为 $0$ 入度点，但因为加入了新边而变为 $1$ 入度点。即在 ② 中产生的点。
次 $0$ 入度点会影响“$u$ 为唯一的 $0$ 入度点”这一判断。若存在次 $0$ 入度点 $v$ ，其入边起点已经被删，则目前就是一个 $0$ 度点。
考虑最大的次 $0$ 入度点 $v$ ，若有 $v>u$ ，则通过将 $v$ 设置为 $P_{i-1}$ （只是方案存在性证明，不必真的设置。不难发现这也符合前面的性质），可以使得 $v$ 在此时恰好变为“真·$0$ 入度点”。
这样我们就能放心地给 $u$ 加边了。
用小根堆维护“$0$ 入度点”，大根堆维护“次 $0$ 入度点”即可。复杂度为 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#define MaxN 200500
using namespace std;
priority_queue<int> q0,q1;
vector<int> g[MaxN];
int n,m,k,tn,P[MaxN],tP[MaxN],d[MaxN];
void del(int u)
{
P[++tn]=u;
for (int i=0;i<g[u].size();i++)
if (!--d[g[u][i]])q0.push(-g[u][i]);
}
bool fl[MaxN];
int main()
{
scanf("%d%d%d",&n,&m,&k);
int savk=k;
for (int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
g[u].push_back(v);d[v]++;
}
for (int u=1;u<=n;u++)
if (d[u]==0)q0.push(-u);
int tn=0;
while(!q0.empty()||!q1.empty()){
if (!q0.empty()){
int u=-q0.top();q0.pop();
if (!k||(q0.empty()&&(q1.empty()||q1.top()<u)))del(u);
else {k--;fl[u]=1;q1.push(u);}
}else {del(q1.top());q1.pop();}
}
for (int i=1;i<=n;i++){
printf("%d ",P[i]);
tP[P[i]]=i;
}
printf("\n%d\n",savk-k);
for (int i=1;i<=n;i++)
if (fl[i])printf("%d %d\n",P[tP[i]-1],i);
return 0;
}
```