「NOIP十连赛day1」散步walk - 拆点最短路 | Bill Yang's Blog
0%

「NOIP十连赛day1」散步walk - 拆点最短路

题目大意


初步想法

首先这道题肯定不能暴力建边。
题目中与运算这个条件非常的特殊,如果不暴力建边,就要考虑如何添加辅助点/边,使得和原题等价。

考虑到权值最大为$2^{20}=1048576$,那么可以将权值加入复杂度的考虑内。
因为子集关系的权值为1,那么我们将权值建成$2^{20}$个点,一个权值到子集的权值连一条边权为0的边,每个点到它的权值连一条边权为1的边,权值到点连一条边权为0的边,这样就和题意等价了。
因为点边太多,使用dijkstra要超时。考虑到边权只可能为0或1,因此我们可以采用Bfs的方法,只要先扩展边权为0的结点,再扩展边权为1的结点就可以保证无误。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1248580;
int n,m,Dist[maxn],cnt=1<<20;
queue<int>Q;
vector<int>edges[maxn],edges0[maxn];
void AddEdge1(int x,int y) {
edges[x].push_back(y);
}
void AddEdge2(int x,int y) {
edges0[x].push_back(y);
}
void Dfs(int Now,int dist) { //扩展边权为0的边
if(Dist[Now]>=0)return;
Q.push(Now);
Dist[Now]=dist;
for(int i=0; i<edges0[Now].size(); i++) {
int Next=edges0[Now][i];
Dfs(Next,dist);
}
if(Now>=cnt)return;
for(int i=0; i<20; i++)
if(Now&(1<<i))Dfs(Now^(1<<i),dist);
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++) {
int x=Get_Int();
AddEdge1(cnt+i,x);
AddEdge2(x,cnt+i);
}
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge1(cnt+x,cnt+y);
}
for(int i=0; i<=cnt+n; i++)Dist[i]=-1;
Dfs(cnt+1,0);
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
Dfs(Next,Dist[Now]+1);
}
}
for(int i=1; i<=n; i++)printf("%d\n",Dist[cnt+i]);
return 0;
}
姥爷们赏瓶冰阔落吧~