A Huster

0%

Shortest-road

Posted on Edited on Valine:

前言

​ 这个本来应该在从外地学习回来之后就因该写的,但是只写了一半,不过看看自己以前写的,果然还是理解太浅了;

正文

也许有很多人觉得最短路就是那几个算法，不过也确实，但是我们的难点主要在建图上。

但是既然是基础，那么就应该好好掌握做法，多敲几遍就好了。

最短路主要的几个算法有 $\text{Dijkstra,floyd,Bellman-ford}$ 和$\text{SPFA}$，而SPFA是Bellman-ford的队列优化，所以一般用SPFA算法。

Floyed

我们先来看floyd，这是一个 $O(n^3)$ 算法，在大部分的题中是会超时的，但是我们在一些题中会发现一些巧妙地运用，之后我们会见到

模板题：

牛大赛Cow Contest

FJ的N(1 <= N <= 100)头奶牛们最近参加了场程序设计竞赛:)。在赛场上，奶牛们按1..N依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。 整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1 <= A <= N; 1 <= B <= N; A != B) ，那么她们的对决中，编号为A的奶牛总是能胜出。 FJ想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 M(1 <= M <= 4,500)轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。

这道题就是一个简单地转换，我们只要看可以判断出的前面的牛+后面的牛=n-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
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int n,m,e[107][107],ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,a,b;i<=m;i++){
        scanf("%d%d",&a,&b);
        e[a][b]=1;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i!=j&&e[i][k]&&e[k][j])
                    e[i][j]=1;        
            }
        }
    }
    for(int i=1;i<=n;i++){
        int r=0;
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            if(e[i][j]||e[j][i]) r++;
            else break;
        }
        if(r==n-1) ans++;
    }
    printf("%d",ans);
}

分治Floyed(update)

​ $\text{Floyed}$ 的本质是动规,而且能够看出,最外层的枚举,即经过点的枚举,可以分开枚举,我们用这种技巧可以得到不经过某个点两点之前最短路,我之前的一次模拟赛就考到了这道题;

​ 与其类似的是 2016计蒜之道复赛A[百度地图的实时路况];

​ 于是我将这道题加入,深刻理解一下Floyed的插点枚举;

给你一个 $n$ 个点的图,定义 $d(x,y,z)$ 是不经过点 $y$ , $x$ 到 $z$ 最短路径的长度,求

​ 考虑Floyed的插点枚举,那么我们分治使枚举分开,并且有效地利用已经枚举的信息.

​ 流程即:枚举经过的点,而分治可以让我们分开枚举,当分治到一个点时,这个点时没有枚举的,统计答案;

​ 模拟: 在分治区间 $[L,R]$ 时,此时在此区间中的点我们还没有枚举过,首先记录初始 $dis$ ,以便我们之后使用,之后将 $[L,mid]$ 的点枚举,去分治 $[mid+1,R]$ 中的点,之后递归回来时,消除枚举区间 $[L,mid]$ 对 $dis$ 的影响,即恢复至之前记录的值,再枚举区间 $[mid+1,R]$ ;

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
#include<bits/stdc++.h>
#define maxn 307
#define ll long long
using namespace std;
int n,m,dis[maxn][maxn];

template<typename type_of_scan>
inline void scan(type_of_scan &x){
	type_of_scan f=1;x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	x*=f;
}
template<typename type_of_print>
inline void print(type_of_print x){
	if(x>9) print(x/10);
	putchar(x%10+'0');
}

ll solve(int l,int r){
	ll ans=0;
	if(l==r){
		for(int i=1;i<=n;i++){
			if(i==l) continue;
			for(int j=1;j<=n;j++){
				if(j==l) continue;
				ans+=1ll*dis[i][j];
			}
		}
		return ans;
	}
	int mid=l+r>>1,other[maxn][maxn];
	memcpy(other,dis,sizeof other);
	for(int k=l;k<=mid;k++){
		for(int i=1;i<=n;i++){
			if(dis[i][k]==-1) continue;
			for(int j=1;j<=n;j++){
				if(i==j) continue;
				if(dis[k][j]==-1) continue;
				if(~dis[i][j]) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
				else dis[i][j]=dis[i][k]+dis[k][j];
			}
		}
	}
	ans+=solve(mid+1,r);
	memcpy(dis,other,sizeof dis);
	for(int k=mid+1;k<=r;k++){
		for(int i=1;i<=n;i++){
			if(dis[i][k]==-1) continue;
			for(int j=1;j<=n;j++){
				if(i==j) continue;
				if(dis[k][j]==-1) continue;
				if(~dis[i][j]) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
				else dis[i][j]=dis[i][k]+dis[k][j];
			}
		}
	}
	ans+=solve(l,mid);
	return ans;
}

int main(){
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	scan(n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scan(dis[i][j]);
	printf("%lld\n",solve(1,n));
	return 0;
}
/*
4
0 1 -1 -1 
-1 0 1 -1 
-1 -1 0 1 
1 -1 -1 0
*/

(注:这是我考试时的代码,题面略有不同,如不连通时最短路为-1,请注意);

bitset优化Floyed(update)

​ bitset是一个存0/1串的类似数组的东西,但是其类似于二进制运算,速度快;

例题

度量一个有向图联通情况的一个指标是连通数，指图中可达顶点对个的个数。

给一个 $n(n<=2000)$ 个节点的连通图,求连通数;

​ 直接跑Floyed是绝对会超时的,但是bitset可以在其中优化转移,这一步:

1
dis[i][j]|=dis[i][k]|dis[k][j]

​ 可以转化成这一步

1
dis[i]|=dis[k](dis[i][k]==true)

​ 这应该就很显然了;

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
#include<bits/stdc++.h>
#define maxn 2007
using namespace std;
int n,ans;
bitset<maxn>a[maxn];

template<typename type_of_scan>
inline void scan(type_of_scan &x){
	type_of_scan f=1;x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	x*=f;
}
template<typename top,typename... tops>
inline void scan(top &x,tops&... X){
	scan(x),scan(X...);
}

int main(){
	scan(n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			char s=getchar();
			while(s!='1'&&s!='0') s=getchar();
			a[i][j]=s-'0';
		}
		a[i][i]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[j][i]) a[j]|=a[i];//只有这一步有差别
		}
	}
	for(int i=1;i<=n;i++) ans+=a[i].count();//统计时count可以加快速度
	printf("%d\n",ans);
}

Dijkstra

由于原来的Dijkstra太慢，就算加上链式前向星，也不能优化多少;

所以我们直接来看堆优化的Dijstra;

Code(Dijkstra)
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
#include<bits/stdc++.h>
#define allom 100007
#define INF 2147483647;
using namespace std;
int s,n,m,cent=1;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
struct node{int next,to,w;}edge[500001];
int vis[allom],head[500001],dis[allom];

template<typename type_of_scan>
void scan(type_of_scan &x){
    type_of_scan f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}

void add(int a,int b,int w){
    edge[cent].next=head[a];
    edge[cent].to=b;
    edge[cent].w=w;
    head[a]=cent;
    cent++;
}

void Dijkstra(int s){
    dis[s]=0;
    q.push(make_pair(dis[s],s));
    while(!q.empty()){
        int x=q.top().second;q.pop();
        if(vis[x]) continue;vis[x]=1;
        for(int i=head[x];i;i=edge[i].next){
            int k=edge[i].to;
            if(dis[k]>edge[i].w+dis[x]){
                dis[k]=edge[i].w+dis[x];
                q.push(make_pair(dis[k],k));
            }
        }
    }
    for(int f=1;f<=n;f++) printf("%d ",dis[f]);
}

int main(){
    scan(n),scan(m),scan(s);
    for(int i=1;i<=n;i++) dis[i]=INF;
    for(int i=1,a,b,c;i<=m;i++){
        scan(a),scan(b),scan(c);
        add(a,b,c);
    }    
    Dijkstra(s);
    return 0;
}
Code(SPFA)
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
#include<bits/stdc++.h>
#define allom 100007
#define INF 0x3f3f3f
using namespace std;
struct node{
    int next,to,w;
}edge[500005];
int n,m,s,cent,head[500005],vis[allom];
int dis[allom];
queue<int >q;

void add(int u,int v,int w){
    edge[++cent]=(node){head[u],v,w};head[u]=cent;
}

void SPFA(int s){
    for(int i=1;i<=n;i++) dis[i]=INF;
    dis[s]=0;
    q.push(s),vis[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop(),vis[u]=0;
        for(int i=head[u],k;i;i=edge[i].next){
            k=edge[i].to;
            if(dis[k]>dis[u]+edge[i].w){
                dis[k]=dis[u]+edge[i].w;
                if(!vis[k]) q.push(k),vis[k]=1;
            }
        }
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1,a,b,c;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    SPFA(s);
    for(int i=1;i<=n;i++){
        dis[i] == INF ? printf("2147483647") : printf("%d",dis[i]);
        if(i!=n) printf(" ");
    }
}

​ 当然，这个只是一个模板，其中SPFA在稠密图中会退变为O（mn）算法，此时Dijkstra的优势就出来了。

​ 注意:Dijkstra一般不去跑负权值图,如果想要去跑了话,要add许多东西,这不在我们的讨论范围之内;

​ 有人说SPFA它死了，但是它还没有凉透，在判断负环中仍有着不可替代的作用，而且在大部分图是稀疏图时，SPFA是跑得飞快,判负环时dfs-Floyed更快。

​ 所以根据数据范围自行选择，一般在遇见边大于200000而没有缩点时，可以果断扔SPFA了；

然后我们主要介绍几个最短路的类型：

1.分层图

分层图主要用于一些较为特殊的题目，比如说

冻结

给一张 $n$ 个点 $m$ 条边的无向图,每个边有一个权值 $w$ ,有 $k$ 次机会将一个边的边权变成 $w/2$ ,求从 $1$ 到 $n$ 的最短路;

​ 分层图模版题,我们将使用次数看成一个状态,分别建 $k$ 个图,相邻两个图之间连接用权值的一半即可;

​ update:好像可以设每个点的状态,最短路时转移即可;

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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<utility>
#include<map>
#include<cstdlib>
#define maxn 10000007
using namespace std;
int n,m,k,head[maxn],dis[maxn],vis[maxn],cent,ans=2147483647;
struct node{int next,to,w;}edge[2*maxn];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int ,int> > >q;
int point(int a,int b){return a+b*n;} 
void add(int u,int v,int w){
    edge[++cent]=(node){head[u],v,w};head[u]=cent;
}

template<typename type_of_scan>
inline void scan(type_of_scan &x){
    type_of_scan f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
} 

void Dijkstra(int s){
    for(int i=1;i<=n*k+n+1;i++) dis[i]=124563335;
    dis[s]=0;
    q.push(make_pair(dis[s],s));
    while(!q.empty()){
        int x=q.top().second;q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=edge[i].next){
            int y=edge[i].to;
            if(dis[y]>dis[x]+edge[i].w){
                dis[y]=dis[x]+edge[i].w;
                q.push(make_pair(dis[y],y));
            }
        }
    } 
}

int main(){
    scan(n),scan(m),scan(k);
    for(int i=1,a,b,w;i<=m;i++){
        scan(a),scan(b),scan(w);
        for(int j=0;j<=k;j++) add(point(a,j),point(b,j),w),add(point(b,j),point(a,j),w);
        for(int j=0;j<=k;j++) add(point(a,j),point(b,j+1),w/2),add(point(b,j),point(a,j+1),w/2);
    }
    Dijkstra(1);
    for(int i=0;i<=k;i++) ans=min(ans,dis[point(n,i)]);
    printf("%d",ans);
}

2.同余建图

​ 这道题算是思路清奇,于是就将其展示出来(当时就是这道题导致整个博客咕咕了)

跳楼机

有一个 $h$ 层的楼房,一个跳楼机可以选择跳 $x,y,z$ 层或者跳回一楼,求能跳到的楼层数;

​ 这道题思路并不好想,说是同余,主要是因为统计答案时与跑最短路优化数组大小的方式罢了;

​ 先考虑如何统计答案,如果我们知道一个数 $num$ 是由 $y,z$ 构成的,即 $num=ay+bz$ ,那么如果加上 $x$ ,它能到达的楼层数为 $(h-num)/x+1$ 其中 $+1$ 是因为要统计不加 $x$ 时的答案;

​ 那么如果我们能找到这些数,再去统计不就好了吗,但是会有重复,而且数字太过庞大,无法完全跑出,那么考虑什么时候回重复计数,即当 $num1=num2+ax$ ,此时 $num1$ 的贡献已经被 $num2$ 统计过,再观察两个数字,发现 $num1 \% x=num2 \% x$ ,那么我们只要找到余数相同中最小值即可,余数共有 $x$ 种;

​ 设计转移方程: 设 $f[i]$ 指余数为 $i$ 时最小楼层数,那么转移有两种方式;

​ $f[(i+y)\%x]=min(f[i]+y,f[(i+y)\%x])$

​ $f[(i+z)\%x]=min(f[i]+z,f[(i+y)\%x])$

​ 我们可以用最短路来优化类似于点 $i$ 与点 $(i+y)\%x$ 连边,代价为 $y$ ;

​ 讲到这应该就够了,这里附上的代码是我以前写的,有点丑,但是能看懂;

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
#include<bits/stdc++.h>
#define INF 1000000000000000LL
#define ll long long
#define maxn 100007
using namespace std;
ll h,dis[maxn];
int a[4],x,y,z,mn,vis[maxn];
int min(int x,int y){return x<y?x:y;}
queue<int >q;const int n=3;

void SPFA(){
	memset(dis,0x3f3f3f3f,sizeof(dis));
	vis[1]=1;q.push(1);dis[1]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=1;i<=n;i++) if(a[i]!=mn){
			int y=(a[i]+x)%mn;
			if(dis[y]>dis[x]+a[i]){
				dis[y]=dis[x]+a[i];
				if(!vis[y]) vis[y]=1,q.push(y);
			}
		}
		vis[x]=0;
	}
}

ll query(ll x){
	ll ans=0;
	for(int i=0;i<mn;i++){
		if(x>=dis[i]) ans+=(x-dis[i])/mn+1; 
	}
	return ans;
}

int main(){
//	freopen("srwudi.in","r",stdin);
//	freopen("srwudi.out","w",stdout);
	scanf("%lld%d%d%d",&h,&x,&y,&z);
	mn=min(x,min(y,z));
	if(x==1||y==1||z==1){
		printf("%lld",h);
		return 0;
	}
	a[1]=x,a[2]=y,a[3]=z;
	SPFA();
	printf("%lld",query(h));
	return 0;
}

3.另类的建图方式

​ 线段树,树剖优化建图,倍增优化建图,然后再去跑最短路,但这个我并不是非常想说,先咕咕了;

TO BE CONTINUE
本站访问次数：