「POI2013」Price List-图论

给定一个 $n$ 个点,$m$ 条边的无向联通图,每条边的权值均为 $a$。

原图所有满足 $u$ 节点和 $v$ 节点间最短路为 $2 \times a$ 的点对 $(u,v)$ 间建立一条无向边,边的权值均为 $b$。

给定一个起始节点$k$,求在上述操作后,$k$到所有节点的最短路径。

链接

Luogu P3547

题解

第一遍写觉得是sb题,第二遍觉得是神题oooorz

可以发现,一共有三种从k点到达其他点的方式:

  • 全走$a$边
  • 走$0/1$条边的$a$,剩下沿最短路走$b$
  • 全走$b$边(可能绕远)

第一种和第二种情况可以一遍$bfs$解决,这也就是我所想到的了。

然后交上去,$WA$。


第三种情况如果直接两次往外扩展建边,那么复杂度是$O(m^2)$。

这个时候我们有一个微小的优化,就是建两份的图,分别用作从一个点第一次和第二次扩展的用的边。

每次我们两次扩展,都把所有合法的第二次扩展的边删掉,理由是非常显然的,因为我们已经访问到了这个节点,根据bfs的性质,所有这个节点在第二张图的入边都不需要了,所以就可以删掉。

然后复杂度是$O(m \sqrt{m})$。

具体证明如下:

点击切换显示状态

首先,时间复杂度约等于遍历的边的数量,所以我们只需要考虑那些遍历了却没被删掉的边的数量。

对于每一个节点$x$,由他开始只会进行一次遍历再二次遍历中,没被删掉的边只有一种,就是在二次遍历中遍历到了一个仍然与$x$距离为$1$的点,也就是一个三元环。

所以对于这个节点x,假设和他距离为$1$的点有$k$个(也就是这个节点的度数),那么对于每一次二次遍历,那么最多有$k^2$条边遍历过但没有被删掉,只有这些边有可能在接下来的遍历中被再次遍历,又因为第一次遍历的边总共是$m$条,所以总时间复杂度就是它们的相乘。
$$
\sum_{v \in V} \min(deg(v)^2,m) \leq \sum_{v \in V} \sqrt{deg(v)^2 \cdot m} = \sqrt {m} \sum_{v \in V} deg(v) = O(m \sqrt{m})
$$


参考:
CSDN

这个题告诉我们:适当删边可能降低一些复杂度。

orz出题人…

代码

点击切换显示状态
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
110
111
112
113
114
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 210000,MAXM = 210000;

struct Graph{
int to[MAXM],nex[MAXM],pre[MAXM];
int fir[MAXN];int ecnt;
Graph(){
ecnt = 1;
}
void addedge(int u,int v){
int e = ecnt;
pre[fir[u]] = e;
to[e] = v,nex[e] = fir[u],pre[e] = 0;
fir[u] = e;
ecnt++;
}
void deledge(int x,int e){
int n = nex[e],p = pre[e];
if(!p) fir[x] = n;
nex[p] = n,pre[n] = p;
}
}A,B;

int n,m,k,a,b;
long long ans[MAXN];

long long dis[MAXN];
queue<int> q;


void init(){
scanf("%d %d %d %d %d",&n,&m,&k,&a,&b);
int u,v;
for(int i = 1;i<=m;i++){
scanf("%d %d",&u,&v);
A.addedge(u,v),A.addedge(v,u);
B.addedge(u,v),B.addedge(v,u);
}
}

void bfs1(){
while(!q.empty()) q.pop();
for(int i = 1;i<=n;i++) dis[i] = 1000000;
dis[k] = 0;q.push(k);
while(!q.empty()){
int nown = q.front();q.pop();
for(int nowe = A.fir[nown];nowe;nowe = A.nex[nowe]){
int v = A.to[nowe];
if(dis[v] > dis[nown] + 1){
dis[v] = dis[nown] + 1;
q.push(v);
}
}
}
for(int i = 1;i<=n;i++)
ans[i] = min(dis[i] * a,(dis[i]/2) * b + (dis[i]%2) * a);
}

void bfs2(){
static bool vis[MAXN];
while(!q.empty()) q.pop();
for(int i = 1;i<=n;i++)
dis[i] = 1000000;
dis[k] = 0;q.push(k);
while(!q.empty()){
int nown = q.front();q.pop();
vis[nown] = 1;
for(int e1 = A.fir[nown];e1;e1 = A.nex[e1]){
int v1 = A.to[e1];
vis[v1] = 1;
}
for(int e1 = A.fir[nown];e1;e1 = A.nex[e1]){
int v1 = A.to[e1];
for(int e2 = B.fir[v1];e2;e2 = B.nex[e2]){
int v2 = B.to[e2];
if(!vis[v2]){
// printf(" v2:%d\n",v2);
if(dis[v2] > dis[nown] + 1){
dis[v2] = dis[nown] + 1;
q.push(v2);
}
B.deledge(v1,e2);
}
}
}
for(int e1 = A.fir[nown];e1;e1 = A.nex[e1]){
int v1 = A.to[e1];
vis[v1] = 0;
}
vis[nown] = 0;
}
for(int i = 1;i<=n;i++)
ans[i] = min(ans[i],dis[i] * b);
}

void solve(){
memset(ans,0x3f,sizeof(ans));
bfs1();
bfs2();
for(int i = 1;i<=n;i++){
printf("%lld\n",ans[i]);
}
}

int main(){
init();
solve();
return 0;
}