Diligent-OI R2 C 题解

出题人题解。

首先显然能注意到：将图看成连通图后，同一个连通块里的就能相互转移。于是，每个点的答案肯定是连通块里的最大值之一转移到的。

这个题中，一条边相对于某个点来说是入边还是出边已经不重要了，因为都可以通过这条边进入或走出某个点。于是为了方便并不产生误导，将原来的某个点的入边称为 A 边，原来某个点的出边称为 B 边。

不难发现，从一个点的 A 边进入某个点，再从 B 边出去，这种情况不消耗代价，B 边进入、A 边出去也一样。只有从一个点的 A 边进入、A 边出去，或者 B 边进入、B 边出去，才会消耗

1

步。

于是，对于每个点，我们需要考虑的边有四类：从 A 边或 B 边进来或出去都需要考虑。于是不难想到拆点：

然后，所有原图中的边

u\rarr v

可以拆成两条：

u

的 B2 连向

v

的 A1、从

v

的 A2 连向

u

的 B1。

显然这样的拆点方式，仅仅使得点和边的规模都扩大了常数倍。其实可以合并 A1 和 B2，再合并 A2 和 B1，做到一个点仅拆成两个点。但是为了较好理解还是选择了上面的方法。

最后每个连通块独立，在新图中跑 01bfs 即可。因为最大值可能有多个，所以把它们都设为起点。

时间复杂度

O(n+m)

。

以下是由 jasmine0201编写的代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,M=2*N;
int n,m,d[4*N],a[4*N],b[4*N],s[4*N];
struct edge1 {int cnt,head[4*N],nxt[4*M],to[4*M],w[4*M]; } ed;
struct edge2 {int cnt,head[N],nxt[M],to[M]; } Ed;
void addedge(int u,int v,int p){
	ed.to[++ed.cnt] = v;
	ed.nxt[ed.cnt] = ed.head[u];
	ed.head[u] = ed.cnt;
    ed.w[ed.cnt] = p;
}
void addEdge(int u,int v){
	Ed.to[++Ed.cnt] = v;
	Ed.nxt[Ed.cnt] = Ed.head[u];
	Ed.head[u] = Ed.cnt;
}
int dfs(int x){
	if(b[x]) return s[x];
	b[x]=1;
	s[x]=a[x];
	// for(int i=0;i<Ed[x].size();i++) s[x]=max(s[x],dfs(Ed[x][i]));
    for(int i=Ed.head[x];i;i=Ed.nxt[i]) s[x]=max(s[x],dfs(Ed.to[i]));
	return s[x];
}
void dfs1(int x,int num){
	if(s[x]==-1) return;
	s[x]=-1;
	if(a[x]<num) b[x]=0;
	// for(int i=0;i<Ed[x].size();i++) dfs1(Ed[x][i],num);
    for(int i=Ed.head[x];i;i=Ed.nxt[i]) dfs1(Ed.to[i],num);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
	int n;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		addedge(i*4+1,i*4+3,0);
		addedge(i*4+2,i*4+4,0);
		addedge(i*4+1,i*4+4,1);
		addedge(i*4+2,i*4+3,1);
	}
	int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		addedge(u*4+3,v*4+1,0);
		addedge(v*4+4,u*4+2,0);
		addEdge(u,v);
		addEdge(v,u);
	}
	for(int i=1;i<=n;i++) dfs(i);
	for(int i=1;i<=n;i++) dfs1(i,s[i]);
	deque<int> q;
	for(int i=1;i<=n;i++){
		if(b[i]){
			q.push_back(i*4+1); d[i*4+1]=1;
			q.push_back(i*4+2); d[i*4+2]=1;
		}
	}
	while(!q.empty()){
		int x=q.front();q.pop_front();
		for(int i=ed.head[x];i;i=ed.nxt[i]){
			int v=ed.to[i];
			if(d[v]<=d[x]+ed.w[i]&&d[v]!=0) continue;
			d[v]=d[x]+ed.w[i];
			if(ed.w[i]==0) q.push_front(v);
			else q.push_back(v);
		}
	}
	for(int i=1;i<=n;i++){
		if(b[i]) cout<<0<<' ';
		else cout<<min(d[i*4+3],d[i*4+4])<<' ';
	}
}

Diligent-OI R2 C 题解

文章操作

相关推荐

评论

Diligent-OI R2 C 题解