我觉得这道题评成紫题挺有道理的
# 题意
> Linked 洛谷 P3243
点击展开/折叠 题意
有 $n$ 道菜准备上桌，上桌有一些要求：
- 有 $m$ 个形如 $(a,b)$ 的限制，表示 $a$ 必须比 $b$ 先上；
- 在满足第一条限制的前提下，尽可能使菜肴 $1$ 上桌的时间尽可能靠前；
- 在满足前两条限制的前提下，使菜肴 $2$ 上桌的时间尽可能靠前；
- 在满足前三条限制的前提下，使菜肴 $3$ 上桌的时间尽可能靠前；
- 以此类推。
求最优的上菜次序，或判断无解。
$1\le n,m\le10^5$
# 解析
先把题目看懂，并不是字典序最小（样例也会告诉你这一点）。
把题目图形化，给定的 $m$ 条先后顺序 $(a,b)$ 相当于是有向边 $(b,a)$，即 $a$ 比 $b$ 先上；显然有解就必须无环，也就是 DAG。
DAG 就容易想到拓扑，但是好像并不能直接拓扑？
G[u] 表示 $u$ 能够到达的所有点（DAG上的后继）的导出子图
实际上，假如现在没有上桌的最小的菜是 $h$，则 $h$ 应当只考虑 $h$ 的后继；而非 $h$ 后继的菜可以后上，否则 $h$ 上菜的时间会延后。
然后可以非常暴力地 $O(n^2)$ 来模拟这个过程，（一个非常不标准的）伪代码应该是：
1
2
3
4
5
6
7
8
9
| function Solve(G){
if G = empty then
return
for v = min{G} then
remove v from G
Solve(G[v])
ans:=ans+v
}
|
这个暴力无法优化，其瓶颈在于动态维护 G[u] 中的最小值，即动态维护 DAG 中一个点的所有后继的最小值。
但是我们发现，记求出的答案序列的最后一个点为 $w$：
- 首先 $w$ 一定没有后继，即没有出度；
- 并且 $w$ 是所有没有出度的节点中最大的一个。
从原图中删去 $w$，再对这个图用 Solve(G) 求解，我们仍然可以得到答案序列的最后一个元素 $w_2$ 是该图中没有出度的节点中最大的一个。
如果把原图 $G$ 的边全部反过来，显然新图 $G’$ 仍然是 DAG，而 $w$ 就是所有没有入度的点中最大的一个；$w_2$ 是删去 $w$ 后没有入度的点的最大的一个……
于是就可以证明，答案序列倒过来就是对 $G’$ 做优先取较大点的拓扑排序。
真是巧妙至极，虽然结论很容易意会甚至可能可以猜到，但是真的弄懂原因还是感觉非常震撼 awa
# 源代码
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
49
50
51
52
53
54
55
56
57
58
59
|
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
#define ci const int &
struct GRAPH{
int head[N],nxt[N],to[N],du[N],ncnt;
void AddEdge(ci u,ci v){
int p=++ncnt;
to[p]=v,nxt[p]=head[u],head[u]=p;
du[v]++;
}
void Init(ci n){
for(int i=1;i<=n;i++)
head[i]=0,du[i]=0;
ncnt=0;
}
inline int operator [](ci u){return head[u];}
}Gr;
int n,m,cas,ans[N];
priority_queue<int> que;
inline int Read(int &r){
int b=1,c=getchar();r=0;
while(c<'0' || '9'<c) b=c=='-'? -1:b,c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
return r*=b;
}
int main(){
Read(cas);
while(cas--){
Read(n),Read(m);
Gr.Init(n);
for(int i=1,u,v;i<=m;i++)
Read(u),Read(v),Gr.AddEdge(v,u);
for(int i=1;i<=n;i++)
if(!Gr.du[i])
que.push(i);
int nans=n;
while(!que.empty()){
int u=que.top();que.pop();
ans[nans--]=u;
for(int it=Gr[u];it;it=Gr.nxt[it])
if(!(--Gr.du[Gr.to[it]]))
que.push(Gr.to[it]);
}
if(nans) printf("Impossible!\n");
else for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n? '\n':' ');
}
return 0;
}
|
THE END
Thanks for reading!
> Linked 云鸟-网易云