【题解】10-5提高组模拟

图论做爽了

A. [蓝桥杯 2024 省 B 第二场] 狡兔 k 窟

lnk

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
// Problem:Luogu P12126 [蓝桥杯 2024 省 B 第二场] 狡兔 k 窟

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=5010;
int n,q,c[MAXN];
vector <int> id[MAXN];
struct edge
{
	int v,w;
};
vector <edge> g[MAXN];
struct node
{
	int u,dis;
	bool operator <(const node a)const
	{
		return dis>a.dis;
	}
};
priority_queue <node> pq;
int dis[MAXN];
void dijkstra(int s)
{
	memset(dis,0x3f,sizeof(dis));
	pq.push({s,0});
	dis[s]=0;
	while(!pq.empty())
	{
		node front=pq.top();
		pq.pop();
		int u=front.u;
		if(dis[u]!=front.dis)continue;
		for(auto tmp:g[u])
		{
			int v=tmp.v,w=tmp.w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				pq.push({v,dis[v]});
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		g[c[u]].push_back({c[v],1});
		g[c[v]].push_back({c[u],1});
	}
	for(int i=1;i<=q;i++)
	{
		int s,t;
		cin>>s>>t;
		dijkstra(c[s]);
		cout<<dis[c[t]]<<'\n';
	}
	return 0;
}

B.「Diligent-OI R2 C」所谓伊人

lnk

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
// Problem:Luogu P13823 「Diligent-OI R2 C」所谓伊人

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10,MAXM=MAXN<<1;
int n,m,p[MAXN];
vector <int> g[MAXN];
struct edge
{
	int v,w;
};
vector <edge> G[MAXM];
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int wcc[MAXN],maxp[MAXN],wcnt;
int bfs()
{
	for(int i=1;i<=n;i++) if(wcc[i]==0)
	{
		wcc[i]=++wcnt;
		maxp[wcnt]=p[i];
		queue <int> q;
		q.push(i);
		while(!q.empty())
		{
			int u=q.front();
			q.pop();
			maxp[wcnt]=max(maxp[wcnt],p[u]);
			wcc[u]=wcnt;
			for(int v:g[u])
				if(wcc[v]==0)
				{
					wcc[v]=wcnt;
					q.push(v);
				}
		}
	}
	return 0;
}
bool vis[MAXM];
int dis[MAXM];
void dijkstra()
{
	deque <int> q;
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=n;i++)
		if(p[i]==maxp[wcc[i]])
			q.push_back(i),q.push_back(i+n),
			dis[i]=dis[i+n]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop_front();
		if(vis[u])continue;
		vis[u]=1;
		for(auto tmp:G[u])
		{
			int v=tmp.v,w=tmp.w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				if(w==0)q.push_front(v);
				else q.push_back(v);
			}
		}
	}
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	{
		p[i]=read();
		G[i].push_back({i+n,1});
		G[i+n].push_back({i,1});
	}
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		G[u].push_back({v,0});
		G[v+n].push_back({u+n,0});
		g[u].push_back(v);
		g[v].push_back(u);
	}
	bfs();
	dijkstra();
	for(int i=1;i<=n;i++)
	{
		int ans=min(dis[i],dis[i+n]);
		if(p[i]==maxp[wcc[i]])ans=0;
		cout<<ans<<" ";
	}
}

其他还没订完，先咕着

游记
#集训
【题解】10-5提高组模拟
http://j27egu.github.io/2025/10/06/【题解】10-5提高组模拟/
作者
j27eGU
发布于
2025年10月6日
许可协议