【NOIP2018模拟10.30】Idioms 题解

题目描述

Input
第一行两个整数 $n,m$。
接下来 $m$ 行，每行两个整数 $a_i,b_i$。

Output
输出 $n$ 行，每行一个整数表示以字符 $i$ 开始时游戏会进行的轮数。特别地，如果游戏会无限地进行下去，输出 -1。

Sample Input
4 4
1 2
2 1
3 3
2 4

Sample Output
-1
1
-1
0

Data Constraint

解法：

稍加分析，我们发现最好的思考顺序是从外往内。

即如果希望越少越好，就是拓扑序。

但是发现有环，而且还有另一个希望越长越好的决策者。

每个点的贡献都可以从相邻的点转移，那么考虑设一下状态。

设 $f_{i,0/1}$ 表示以字符 $i$ 开始、第一步决策者是小C/小G的最终轮数。

方程显然如下：
$$\begin{gathered} f_{i,0}=\min (f_{j,1})+1:j\in i_{son} \\ {f}_{i,1}=\max (f_{j,0})+1:j\in i_{son} \end{gathered}$$
那么同样有显然的边界： $f_{i,0/1}=0:i_{son}=\varnothing$ 。

边界可能有多个，可以想到用队列存储，自 $j$ 向 $i$ 转移。

现在问题来了：怎样保证队列里状态的最优性？

• 刚开始的边界，一定是最优的。
• 对于 $f_{i,0}$ ，第一个更新到的一定是最小的（ $bfs$ 的性质满足拓扑序）
• 对于 $f_{i,1}$ ，最后一个更新到的一定是最大的（ $bfs$ 的性质）

所以记录每个点的出度 $c{d}_i$ ，不断在更新中 $--c{d}_i$ 。

当第一次更新到 $f_{i,0}$ ，把 $f_{i,0}$ 加入队列。

当一次更新 $i$ 后 $c{d}_i=0$ ，把 $f_{i,1}$ 加入队列。

这样一来，也不用每次都 $\max ,\min$ 地去转移了。

因为队列里的东西都是最优的，所以每个点只能也只会进队一次。

要注意的是，队列不仅要存点编号，还要存下 $0/1$ ，标记同样。

本质与 $dijkstra$ 类似。

时间复杂度是 $O(m)$ 。

具体实现参考代码：

#include
#define inf 1e9
using namespace std;

const int N=5e5+5;
int n,m,tot,head=1,last,cd[N],final[N],nt[N],to[N],q[N*2][2],f[N][2];

//链式前向星
inline void link(int x,int y) { to[++tot]=y,nt[tot]=final[x],final[x]=tot; }

//输入、建图以及初始化队列
inline void init() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) {
		int x,y;
		scanf("%d%d",&x,&y);
		link(y,x),++cd[x];
	}
	for(int i=1;i<=n;++i) f[i][0]=inf;
	for(int i=1;i<=n;++i) if(!cd[i])
		q[++last][0]=i,q[last][1]=0;
		q[++last][0]=i,q[last][1]=1;
		f[i][0]=0;
}

//更新
inline void bfs() {
	while(head<=last) {
		int x=q[head][0],p=q[head++][1];
		for(int j=final[x];j;j=nt[j]) {
			int i=to[j];
			if(!p) {
				if(!(--cd[i])) {
					f[i][1]=f[x][0]+1;
					q[++last][0]=i,q[last][1]=1; 
				}
			} else if(f[i][0]==inf) {
				f[i][0]=f[x][1]+1;
				q[++last][0]=i,q[last][1]=0;
			}
		}
	}
}

//输出答案
inline void _ans() {
	for(int i=1;i<=n;++i)
	if(f[i][0]==inf) printf("-1\n");
	else printf("%d\n",f[i][0]);
}

//主函数
int main() {
	init(),bfs(),_ans();
}
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