[ABC304Ex] Constrained Topological Sort 做题记录

有 $n$ 个点，每个点有 $l_i,r_i$ 两个值，有 $m$ 条有向边 $(s_i,t_i)$，你要给每个点确定一个权值 $a_i$，满足以下条件：

• $a_i$ 是 $n$ 的排列；
• 对于所有 $1\le i\le m$ 均有 $a_{s_i}<a_{t_i}$；
• 对于所有 $1\le i\le n$ 均有 $l_i\le a_i\le r_i$；

判断无解。

$2\le n\le 2\times 10^5$，$0\le m\le \min(n(n-1),4\times 10^5)$，$i\not=j\Rightarrow s_i\not=s_j$。

不难发现若不是 DAG 则无解。

观察到 $r_{s_i}$ 实际上可以和 $r_{t_i}-1$ 取 $\min$，因为 $a_{s_i}<a_{t_i}$。那么先倒着拓扑一遍求出取完 $\min$ 的 $r_i$。

先来考虑没有 $l_i$ 限制该怎么做，显然拓扑排序的时候每次新入队的 $r_v$ 都会大于把它入队的 $r_u$，那么使用优先队列拓扑，每次选 $r_u$ 最小的 $u$ 来拓展一定是最优的。

考虑有 $l_i$ 限制的情况下怎么办，考虑建立一个“寄存器”$vec$。拓扑前先把所有入度为 $0$ 的点 $u$ 放进 $vec_{l_u}$，然后从 $1$ 到 $n$ 遍历，遍历到 $i$ 时把 $vec_i$ 内的所有元素入队，并取出一个元素 $x$，让 $ans_x=i$ 然后拓展 $x$。$v$ 入队的时候：

• $l_v>i$：先存到 $vec_{l_v}$ 里；
• $l_v\le i$：直接入队；

这样就能保证 $ans_i\ge l_i$，消除了 $l_i$ 的限制。

代码如下：

// Problem: [ABC304Ex] Constrained Topological Sort
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_abc304_h
// Memory Limit: 1 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)\

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

using namespace std;

const int S=200005;

int n,m;
int l[S],r[S];
vector<int> g1[S],g2[S];
int ind[S];
vector<int> idx[S];
int ans[S];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g1[x].push_back(y),g2[y].push_back(x);
	}
	for(int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]);
	queue<int> q;
	for(int i=1;i<=n;i++) ind[i]=g1[i].size();
	for(int i=1;i<=n;i++) if(ind[i]==0) q.push(i);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int v:g2[u])
		{
			r[v]=min(r[v],r[u]-1);
			if(--ind[v]==0) q.push(v);
		}
	}
	for(int i=1;i<=n;i++) if(ind[i]!=0) return puts("No"),0;
	priority_queue<pair<int,int>> q2;
	for(int i=1;i<=n;i++) ind[i]=g2[i].size();
	for(int i=1;i<=n;i++) if(ind[i]==0) idx[l[i]].push_back(i);
	for(int i=1;i<=n;i++)
	{
		for(int j:idx[i]) q2.push(make_pair(-r[j],j));
		if(q2.empty()) return puts("No"),0;
		int u=q2.top().second;
		q2.pop();
		ans[u]=i;
		for(int v:g1[u])
		{
			if(--ind[v]==0)
			{
				if(l[v]>i) idx[l[v]].push_back(v);
				else q2.push(make_pair(-r[v],v));
			}
		}
	}
	for(int i=1;i<=n;i++) if(ans[i]<l[i]||ans[i]>r[i]) return puts("No"),0;
	puts("Yes");
	for(int i=1;i<=n;i++) printf("%d ",ans[i]);
	printf("\n");
	return 0;
}