题解 51nod2883 城市

题解 51nod2883 城市

题面

51nod

解析

首先求出 $S$ 到每个点 $i$ 的距离 $d_i$,并建出最短路图.

如果原图中的一条边 $(x,y,w)$ 满足 $d_x+w=d_y$,那么这条边就在最短路图上.

然后没有在最短路图上的边显然不会有贡献.

考虑最短路图上的一个点 $i$,它会对图中的哪些边产生贡献,

显然是满足去掉这条边后,从 $S$ 就无法到达 $i$ 的边.

因此我们求出每个点 $i$ 的最后的必经点 $pr_i$,并建出必经点树,即连边 $pr_i \to i$.

显然 $pr_i$ 为 $i$ 的所有前驱在树上的 $\texttt{lca}$.

由于最短路图是 $\texttt{DAG}$,所以具体可以用拓扑排序和倍增实现.

为了方便,可以对每条边新建一个点,即把最短路图中的边 $x\to y$ 换成 $x\to z,z\to y$.

最后每条边的答案就是它对应的点的子树大小(边对应的点都不计入大小中).

code

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
108
109
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <algorithm>
#define ll long long
#define filein(a) freopen(a,"r",stdin)
#define fileout(a) freopen(a,"w",stdout);
using namespace std;

inline int read(){
int sum=0,f=1;char c=getchar();
while((c<'0'||c>'9')&&c!=EOF){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'&&c!=EOF){sum=sum*10+c-'0';c=getchar();}
return sum*f;
}

const int N=300005;
struct road{int x,y,w;}a[N];
struct edge{int to,next,w;}e[N<<2];
int n,m,S;
ll d[N],f[N],ans[N];
int pr[N],ind[N],fa[N][20],dep[N];
int head[N],Head[N],HEAD[N],cnt;

inline void add(int *p,int x,int y,int w){
e[++cnt]=(edge){p[x],y,w};p[x]=cnt;
}

inline void dji1(){
priority_queue< pair<int,int> >que;
memset(d,0x3f,sizeof(d));
que.push(make_pair(0,S));d[S]=0;
while(!que.empty()){
int x=que.top().second;que.pop();
for(int i=head[x];i;i=e[i].to){
int k=e[i].next;
if(d[k]<=d[x]+e[i].w) continue;
d[k]=d[x]+e[i].w;
que.push(make_pair(-d[k],k));
}
}
}

inline int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;i--){
if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
}
if(x==y) return x;
for(int i=19;i>=0;i--){
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}

inline void insert(int x){
add(HEAD,pr[x],x,0);
fa[x][0]=pr[x];dep[x]=dep[pr[x]]+1;
for(int i=1;i<=19;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
}

inline void topsort(){
queue<int> que;
que.push(S);dep[S]=1;
while(!que.empty()){
int x=que.front();que.pop();
for(int i=Head[x];i;i=e[i].to){
int k=e[i].next;
ind[k]--;
if(!pr[k]) pr[k]=x;
else pr[k]=lca(pr[k],x);
if(!ind[k]){que.push(k);insert(k);}
}
}
}

inline void dfs(int x){
f[x]=(x<=n);
for(int i=HEAD[x];i;i=e[i].to){
int k=e[i].next;
dfs(k);f[x]+=f[k];
}
}

int main(){
n=read();m=read();
for(int i=1;i<=m;i++){
int x=read(),y=read(),w=read();
add(head,x,y,w);add(head,y,x,w);
a[i].x=x;a[i].y=y;a[i].w=w;
}
S=read();
dji1();
for(int i=1;i<=m;i++){
int x=a[i].x,y=a[i].y,w=a[i].w;
if(d[x]+w==d[y])
add(Head,x,n+i,0),add(Head,n+i,y,0),ind[n+i]++,ind[y]++;
if(d[y]+w==d[x])
add(Head,y,n+i,0),add(Head,n+i,x,0),ind[n+i]++,ind[x]++;
}
topsort();dfs(S);
for(int i=1;i<=m;i++){
int x=a[i].x,y=a[i].y;
ans[x]+=f[i+n];ans[y]+=f[i+n];
}
for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
return 0;
}
感谢您又打赏