2022.08.01 洛谷P7845 「dWoi R2」Change

$$\text{[dWoi R2] }\text{Change}$$

$\text{[Problem]}$

$\text{[Analysis]}$

比较简单的思路。

首先是一个贪心，离起始点 $s$ 越近的边一定越优。

由于 $s$ 不一定可以到达所有的节点，所以我们可以先进行一次拓扑排序（或者 bfs，随便怎么叫），求出 $s$ 到它可以到达的每一个点的距离和 $s$ 出发可以达到哪些点。

不可以到达的点对答案没有任何贡献，所以把所有不可以到达的节点和它的所有相连的边删去，留下所有可以到达的节点，建立一个新的图（这个图一定是原图的子图）。

结合贪心，现在的问题就是求出新图中从 $s$ 到达特定节点 $u$ 的所有路径中必须经过的离 $s$ 最近的那条边（即从 $s$ 到达节点 $u$ 的所有路径的交集中离 $s$ 距离最小的边），记为点 $u$ 的最近必经之路。

记 ${\text{Limit}}_u$ 表示 $u$ 的最近必经之路，考虑节点 $u$ 的所有入边 $(a_i,u)$

1. 如果点 $u$ 的入度为 $1$。考虑 ${\text{Limit}}_a$，如果它不存在（即 $a$ 没有最近必经之路），那么 ${\text{Limit}}_u=(a,u)$，即这条边就是 $u$ 的最近必经之路。
2. 如果点 $u$ 的入度不为 $1$。如果所有 ${\text{Limit}}_{a_i}$ 都相等，那么点 $u$ 有最近必经之路，否则没有（想一想，为什么）。

所以，再来一次拓扑排序即可。

$\text{[code]}$

干讲可能不好理解，加上代码后就好多了。

const int N=5e6+100;
const int mod=998244353;

struct edge{
	int next,to;
}e[N];int h[N],te;
inline void add(int u,int v){
	e[++te]=(edge){h[u],v};h[u]=te;
}

bool Connected[N];
int n,m,s,p,ans,dis[N],ind[N];

inline void bfs(){
	queue<int> q;
	Connected[s]=true;
	memset(dis,127,sizeof(dis));
	dis[s]=0;
	
	for(int i=1;i<=n;i++)
		if (!ind[i]) q.push(i);
	
	while (!q.empty()){
		int u=q.front();q.pop();
		for(int i=h[u];i;i=e[i].next){
			register int v=e[i].to;
			dis[v]=min(dis[v],dis[u]+1);
			if ((--ind[v])==0) q.push(v);
			if (Connected[u]) Connected[v]=true;
		}
	}
}//第一次拓扑，求距离和可达点

vector<int> Graph[N];

inline void Select(){
	for(int u=1;u<=n;u++)
		for(int i=h[u];i;i=e[i].next){
			register int v=e[i].to;
			if (Connected[u]&&Connected[v])
				Graph[u].push_back(v);
		}
	
	memset(ind,0,sizeof(ind));
	memset(h,0,sizeof(h));te=0;
	memset(e,0,sizeof(e));//记得清空原图
	for(int u=1;u<=n;u++) if (Connected[u])
		for(int i=0;i<(int)Graph[u].size();i++){
			add(u,Graph[u][i]);
			++ind[Graph[u][i]];
		}
}//可达点建立新图

int Limit[N];//必经之路 

inline void BFS(){
	queue<int> q;q.push(s);
	memset(Limit,-1,sizeof(Limit));
	
	while (!q.empty()){
		int u=q.front();q.pop();
		for(int i=h[u];i;i=e[i].next){
			register int v=e[i].to;
			if (Limit[v]==-1) Limit[v]=(Limit[u]>0?Limit[u]:i);
			else if (Limit[u]!=Limit[v]) Limit[v]=-2;//无必经之路
			if ((--ind[v])==0) q.push(v);
		}
	}
}//求必经之路

int main(){
	n=read();m=read();
	s=read();p=read();
	
	for(int i=1,u,v;i<=m;i++){
		u=read();v=read();
		add(u,v);++ind[v];
	}//别忘了求原图里的入度
	
	bfs();
	Select();
	BFS();
	
	for(int i=1;i<=n;i++)
		if (Connected[i]&&Limit[i]>0)
			ans=(ans+p-dis[e[Limit[i]].to])%mod;
	
	printf("%lld",1ll*ans*ksm(n,mod-2)%mod);
	
	return 0;
}//ksm:快速幂;read:快读
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91