图论基础之最短路和最小生成树一、最短路二、最小生成树

98 阅读 0 评论 65 点赞

我是靠谱客的博主粗暴芝麻，这篇文章主要介绍图论基础之最短路和最小生成树一、最短路二、最小生成树，现在分享给大家，希望可以做个参考。

一、最短路

1.基础知识

a.Dijkstra算法：基于贪心。具体算法见蓝书P350。但是我个人更习惯从优先队列的bfs角度来理解。所以Dijkstra算法具有两个性质：1.每个点可能被更新多次，但是只能被取出扩展一次。2.当某个点第一次出队时，就已经找到了起点到它的最短路径。

b.Bellman-Ford算法与SPFA算法：Bellman-Ford算法基于迭代思想，而SPFA算法是在Bellman-Ford算法的基础上加入队列优化，可认为算法思想基于bfs。具体可见蓝书P353。

c.Floyd算法：基于动态规划，有方程F(k,i,j)=min(F(k-1,i,j),F(k-1,i,k)+F(k-1,k,j)) （F(k,i,j)表示只经过前k个点中的若干个点，i与j之间的最短路径）。这里着重强调一下简化的方程F(i,j)=min(F(i,j),F(i,k)+F(k,j))。这里的关键在于弄明白为什么F(i,k)与F(k,j)仍处于第k-1层的状态。F(i,k)若被更新，显然有F(i,k)=min(F(i,k),F(i,k)+F(k,k))，其中F(k,k)=0，相当于没有更新，仍处于第k-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
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=210;
int d[N][N],INF=1e9;
int m,n,Q;
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
}
int main(){
cin>>n>>m>>Q;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) d[i][j]=0;
//注意这类涉及两点之间距离的存储需要把d[i][i]置为0
else d[i][j]=INF;
}
}
while(m--){
int a,b,c;
cin>>a>>b>>c;
d[a][b]=min(d[a][b],c);
}
floyd();
while(Q--){
int a,b;
cin>>a>>b;
if(d[a][b]>INF/2) cout<<"impossible"<<endl;
//别忘了玄学判断
else cout<<d[a][b]<<endl;
}
}

2.例题

例题1：AcWing 340.通信线路(堆优化的Dijkstra算法)

这题看到“使得第K+1贵的电缆最便宜”一类的字样，就要考虑二分答案L。我们又发现：答案具有明显的单调性：当二分的值L增大时，最终其排名K就要减小；反之亦然。所以这题采用二分答案，并每次将图转化为无权图（0/1边权图）处理即可。即每次将大于L的边权置为1，其它置为0，求新图的最短路，dist[n]就是边权L的排名，根据排名来确定二分的取值变化。

代码如下：

复制代码

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
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=1005,M=20*N;
int n,m,k;
int head[N],ne[M],to[M],w[M],dist[N],st[N],idx;
void add(int x,int y,int z){
ne[++idx]=head[x];
head[x]=idx;
to[idx]=y;
w[idx]=z;
}
bool spfa(int mid){
queue<int> q;
q.push(1);
memset(dist,0x3f,sizeof dist);
dist[1]=0;
st[1]=true;
while(q.size()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=head[t];i;i=ne[i]){
int j=to[i],s;
if(w[i]>mid) s=dist[t]+1;
else s=dist[t];
if(s<dist[j]){
dist[j]=s;
if(!st[j]){
q.push(j);
st[j]=true;
}
}
}
}
if(dist[n]<=k) return true;
return false;
}
int main(){
cin>>n>>m>>k;
while(m--){
int a,b,w;
cin>>a>>b>>w;
add(a,b,w);
add(b,a,w);
}
int l=0,r=1000000;
while(l<r){
int mid=(l+r)>>1;
if(spfa(mid)){
r=mid;
}
else{
l=mid+1;
}
}
if(r==1000000) cout<<-1<<endl;
else cout<<r<<endl;
return 0;
}

例题2:AcWing 341.最优贸易(SPFA算法)

这题题意一句话概括：求一条1~n的路径，使得该路径上的节点权值的最大值与最小值之差最大（且最大权值节点出现在最小权值节点之后，若路径存在环，也要满足路径序列上存在这样的两个点）。考虑到括号内的条件，想到用在原图上以1为起点，对所有点求一个dmin，即以该点为终点的，且路径上的节点权值的最小值最小。再在反图上以n为起点，对所有点求一个dmax，即以改点为终点的，且路径上的节点权值的最大值最大。那么最终求答案时，求最大的dmax[x]-dmin[x]即可。求法与求最短路相近，但是不能用Dijkstra算法。因为Dijkstra算法是在节点第一次出队时就取得最优值，而这题显然不满足这个条件，因为路径可能存在环，所以环上完全可能存在更小权值的节点去更新答案。所以这题显然应当采用SPFA算法。代码如下：

复制代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e5+5,M=2e6+5;
int h[N],rh[N],ne[M],to[M],idx;
int dmax[N],dmin[N],p[N];
bool st[N];
queue<int> q;
void add(int h[],int x,int y){
ne[++idx]=h[x];
to[idx]=y;
h[x]=idx;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>p[i];
while(m--){
int x,y,z;
cin>>x>>y>>z;
if(z==1){
add(h,x,y);add(rh,y,x);
}
else{
add(h,x,y);add(h,y,x);
add(rh,y,x);add(rh,x,y);
}
}
memset(dmin,0x3f,sizeof dmin);
q.push(1);
dmin[1]=p[1];
while(q.size()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=h[t];i;i=ne[i]){
int j=to[i];
if(dmin[j]>min(dmin[t],p[j])){
dmin[j]=min(dmin[t],p[j]);
if(!st[j]){
st[j]=true;
q.push(j);
}
}
}
}
memset(dmax,-0x3f,sizeof dmax);
memset(st,false,sizeof st);
q.push(n);
dmax[n]=p[n];
while(q.size()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=rh[t];i;i=ne[i]){
int j=to[i];
if(dmax[j]<max(dmax[t],p[j])){
dmax[j]=max(dmax[t],p[j]);
if(!st[j]){
st[j]=true;
q.push(j);
}
}
}
}
int res=0;
for(int i=1;i<=n;i++){
res=max(res,dmax[i]-dmin[i]);
}
cout<<res;
return 0;
}

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
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e5+5,M=2e6+5;
int h[N],rh[N],ne[M],to[M],idx;
int dmax[N],dmin[N],p[N];
bool st[N];
queue<int> q;
void add(int h[],int x,int y){
ne[++idx]=h[x];
to[idx]=y;
h[x]=idx;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>p[i];
while(m--){
int x,y,z;
cin>>x>>y>>z;
if(z==1){
add(h,x,y);add(rh,y,x);
}
else{
add(h,x,y);add(h,y,x);
add(rh,y,x);add(rh,x,y);
}
}
memset(dmin,0x3f,sizeof dmin);
q.push(1);
dmin[1]=p[1];
while(q.size()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=h[t];i;i=ne[i]){
int j=to[i];
if(dmin[j]>min(dmin[t],p[j])){
dmin[j]=min(dmin[t],p[j]);
if(!st[j]){
st[j]=true;
q.push(j);
}
}
}
}
memset(dmax,-0x3f,sizeof dmax);
memset(st,false,sizeof st);
q.push(n);
dmax[n]=p[n];
while(q.size()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=rh[t];i;i=ne[i]){
int j=to[i];
if(dmax[j]<max(dmax[t],p[j])){
dmax[j]=max(dmax[t],p[j]);
if(!st[j]){
st[j]=true;
q.push(j);
}
}
}
}
int res=0;
for(int i=1;i<=n;i++){
res=max(res,dmax[i]-dmin[i]);
}
cout<<res;
return 0;
}

代码方面还要注意反图的建法，只要添加一个rhead数组作为反图的头节点数组即可，不必新加入next、to等数组。因为邻接表只要从头节点开始查询就可以查到，与中间转移的next、to数组无关。

例题3：AcWing 342.道路与航线(最短路在图论问题中的综合应用)

这题还是挺难的，不仅思路不容易想到，代码也及其不好实现。真的是，考试时直接上SPFA暴力求解好吧。（bushi

这里特意规定了航线与道路的权值不同，是否别有用心呢？我们不妨从此出发思考。想到用Dijkstra算法去处理道路部分，而用SPFA算法来求解航线部分。那么我们可以先将道路加入图中，再划分连通块。将连通块视作一个个大“点”，这些点之间会有若干条航线相连。刚才我们提到用SPFA算法求解，其实不用。我们注意到题目中的这句话：事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策：保证如果有一条航线可以从 Ai 到 Bi，那么保证不可能通过一些道路和航线从 Bi 回到 Ai。这句话的意思其实就是：以连通块作为“点”，航线作为边的图无环。又因为题目中说到航线是有向的，所以该图是有向无环图，考虑使用拓扑排序。具体算法流程可见蓝书P358。对时间复杂度进行分析：用纯SPFA解，若数据经过特殊构造，上界为 $oleft ( rp right )$ ；一般情况为 $oleft ( kleft ( r+p right ) right )$ 。用上述算法，复杂度稳定在： $oleft ( t+p+rlogt right )$ ，可以100%地通过所有数据，稳。

复制代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=25001,M=5e4+1;
int n,mr,mp,s,cnt;
vector<int> block[N];//表示用无向边连接的点的连通块
int bid[N];//表示每个点所处的连通块的编号
int head[N],to[3*M],ne[3*M],w[3*M],idx;
int d[N];//表示拓扑排序中的入度数组
int dist[N];
void add(int x,int y,int z){
ne[++idx]=head[x];
to[idx]=y;
w[idx]=z;
head[x]=idx;
}
void dfs(int u,int id){
bid[u]=id;
block[id].push_back(u);
for(int i=head[u];i;i=ne[i]){
int j=to[i];
if(!bid[j]){
dfs(j,id);
}
}
}
queue<int> q;
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII> > heap;
bool st[N];
void dijkstra(int id){
memset(st,false,sizeof st);
for(auto i : block[id]){
heap.push({dist[i],i});
}
while(heap.size()){
PII t=heap.top();
heap.pop();
int ver=t.second;
if(st[ver]) continue;
for(int i=head[ver];i;i=ne[i]){
int j=to[i];
dist[j]=min(dist[ver]+w[i],dist[j]);
//当ver与j之间的边是道路时，这是dij的正常操作；若是航线，则是收敛操作（迭代法）
if(bid[ver]==bid[j]){
st[ver]=true;
heap.push({dist[j],j});
//所以只有ver与j之间的边是道路时，才要进行dij的push操作。
}
else{
if(--d[bid[j]]==0){
q.push(bid[j]);
}
}
}
}
}
void topsort(){
memset(dist,0x3f,sizeof dist);
dist[s]=0;
for(int i=1;i<=cnt;i++){
if(!d[i]) q.push(i);
}
while(q.size()){
int t=q.front();
q.pop();
dijkstra(t);
}
}
int main(){
cin>>n>>mr>>mp>>s;
while(mr--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
for(int i=1;i<=n;i++){
if(!bid[i]){
dfs(i,++cnt);//深搜划分联通块的模板
}
}
while(mp--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
d[bid[b]]++;
}
topsort();
for(int i=1;i<=n;i++){
if(dist[i]>0x3f3f3f3f/2) puts("NO PATH");
else cout<<dist[i]<<endl;
}
return 0;
}

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
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=25001,M=5e4+1;
int n,mr,mp,s,cnt;
vector<int> block[N];//表示用无向边连接的点的连通块
int bid[N];//表示每个点所处的连通块的编号
int head[N],to[3*M],ne[3*M],w[3*M],idx;
int d[N];//表示拓扑排序中的入度数组
int dist[N];
void add(int x,int y,int z){
ne[++idx]=head[x];
to[idx]=y;
w[idx]=z;
head[x]=idx;
}
void dfs(int u,int id){
bid[u]=id;
block[id].push_back(u);
for(int i=head[u];i;i=ne[i]){
int j=to[i];
if(!bid[j]){
dfs(j,id);
}
}
}
queue<int> q;
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII> > heap;
bool st[N];
void dijkstra(int id){
memset(st,false,sizeof st);
for(auto i : block[id]){
heap.push({dist[i],i});
}
while(heap.size()){
PII t=heap.top();
heap.pop();
int ver=t.second;
if(st[ver]) continue;
for(int i=head[ver];i;i=ne[i]){
int j=to[i];
dist[j]=min(dist[ver]+w[i],dist[j]);
//当ver与j之间的边是道路时，这是dij的正常操作；若是航线，则是收敛操作（迭代法）
if(bid[ver]==bid[j]){
st[ver]=true;
heap.push({dist[j],j});
//所以只有ver与j之间的边是道路时，才要进行dij的push操作。
}
else{
if(--d[bid[j]]==0){
q.push(bid[j]);
}
}
}
}
}
void topsort(){
memset(dist,0x3f,sizeof dist);
dist[s]=0;
for(int i=1;i<=cnt;i++){
if(!d[i]) q.push(i);
}
while(q.size()){
int t=q.front();
q.pop();
dijkstra(t);
}
}
int main(){
cin>>n>>mr>>mp>>s;
while(mr--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
for(int i=1;i<=n;i++){
if(!bid[i]){
dfs(i,++cnt);//深搜划分联通块的模板
}
}
while(mp--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
d[bid[b]]++;
}
topsort();
for(int i=1;i<=n;i++){
if(dist[i]>0x3f3f3f3f/2) puts("NO PATH");
else cout<<dist[i]<<endl;
}
return 0;
}

这里再讲解一下有向无环图求最短路的方法：利用拓扑排序，按照拓扑序依次更新每个节点，当某节点入队时，它取得最短路，因为它后面的节点不可能回来更新它。

例题4：AcWing 343.排序(Floyd解决传递闭包问题)

传递闭包的定义：见蓝书P359-360。具体做法挺简单的，但是代码可真不简单：

复制代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=30,M=605;
int n,m;
bool d[N][N],st[N];
char a[M],b[M];
void floyd(){
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
d[i][j]|=d[i][k]&d[k][j];
}
}
}
}
bool check1(){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(d[i][j] && d[j][i]) return false;//有矛盾
if(!d[i][j] && !d[j][i] && i!=j) return false;//不能确定
}
}
return true;
}
bool check2(){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(d[i][j] && d[j][i]) return true;//有矛盾
}
}
return false;
}
void out(int x){
char ans[N];
for(int i=0;i<n;i++){
int r=0;
for(int j=0;j<n;j++){
if(d[j][i]) r++;
}
ans[r]=i+'A';
}
printf("Sorted sequence determined after %d relations: ",x);
for(int i=0;i<n;i++) cout<<ans[i];
puts(".");
}
char ans[N];
int main(){
while(cin>>n>>m,n || m){
int flag=1;
memset(d,false,sizeof d);
for(int i=1;i<=m;i++){
//根据题意，确定第几次可以确定所有关系时其实不必采用二分，直接暴力即可
char re;
cin>>a[i]>>re>>b[i];
d[a[i]-'A'][b[i]-'A']=true;
floyd();;
if(check1()){//确定了全部关系
if(flag!=-1){
for(int i=0;i<n;i++){
int r=0;
for(int j=0;j<n;j++){
if(d[j][i]) r++;
}
ans[r]=i+'A';
}
printf("Sorted sequence determined after %d relations: ",i);
for(int i=0;i<n;i++) cout<<ans[i];
puts(".");
flag=-1;
}
}
}
if(flag==-1) continue;//确定了所有的关系，直接退出
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(d[i][j] && d[j][i]){//出现矛盾
flag=0;
break;
}
if(!d[i][j] && !d[j][i] && i!=j){//无法确定
flag=1;
}
}
if(!flag) break;
}
if(flag){
puts("Sorted sequence cannot be determined.");
continue;
}
int l=1,r=m;
while(l<r){
int mid=(l+r)>>1;
memset(d,false,sizeof d);
for(int i=1;i<=mid;i++){
d[a[i]-'A'][b[i]-'A']=true;
}
floyd();
if(check2()) r=mid;
else l=mid+1;
}
printf("Inconsistency found after %d relations.n",l);
}
return 0;
}

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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=30,M=605;
int n,m;
bool d[N][N],st[N];
char a[M],b[M];
void floyd(){
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
d[i][j]|=d[i][k]&d[k][j];
}
}
}
}
bool check1(){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(d[i][j] && d[j][i]) return false;//有矛盾
if(!d[i][j] && !d[j][i] && i!=j) return false;//不能确定
}
}
return true;
}
bool check2(){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(d[i][j] && d[j][i]) return true;//有矛盾
}
}
return false;
}
void out(int x){
char ans[N];
for(int i=0;i<n;i++){
int r=0;
for(int j=0;j<n;j++){
if(d[j][i]) r++;
}
ans[r]=i+'A';
}
printf("Sorted sequence determined after %d relations: ",x);
for(int i=0;i<n;i++) cout<<ans[i];
puts(".");
}
char ans[N];
int main(){
while(cin>>n>>m,n || m){
int flag=1;
memset(d,false,sizeof d);
for(int i=1;i<=m;i++){
//根据题意，确定第几次可以确定所有关系时其实不必采用二分，直接暴力即可
char re;
cin>>a[i]>>re>>b[i];
d[a[i]-'A'][b[i]-'A']=true;
floyd();;
if(check1()){//确定了全部关系
if(flag!=-1){
for(int i=0;i<n;i++){
int r=0;
for(int j=0;j<n;j++){
if(d[j][i]) r++;
}
ans[r]=i+'A';
}
printf("Sorted sequence determined after %d relations: ",i);
for(int i=0;i<n;i++) cout<<ans[i];
puts(".");
flag=-1;
}
}
}
if(flag==-1) continue;//确定了所有的关系，直接退出
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(d[i][j] && d[j][i]){//出现矛盾
flag=0;
break;
}
if(!d[i][j] && !d[j][i] && i!=j){//无法确定
flag=1;
}
}
if(!flag) break;
}
if(flag){
puts("Sorted sequence cannot be determined.");
continue;
}
int l=1,r=m;
while(l<r){
int mid=(l+r)>>1;
memset(d,false,sizeof d);
for(int i=1;i<=mid;i++){
d[a[i]-'A'][b[i]-'A']=true;
}
floyd();
if(check2()) r=mid;
else l=mid+1;
}
printf("Inconsistency found after %d relations.n",l);
}
return 0;
}

例题5：AcWing 344.观光之旅（Floyd求最小环）

这题是无向图的最小环问题，直接求答案比较简单，只要对Floyd算法的模板简单修改一下即可：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Floyd(){
memcpy(f,a,sizeof a);//f是最短路数组，a是普通路径数组
for(int k=1;k<=n;k++){
for(int i=1;i<k;i++){
for(int j=i+1;j<k;j++){//i,j节点全部取自前k-1个节点，并且不重复
if(ans>(ll)f[i][j]+a[i][k]+a[k][j]){//只有i,j之间的路径上存在多个节点
ans=f[i][j]+a[i][k]+a[k][j];//i,j之间的最短路径上只存在前k-1个节点
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(f[i][j]>f[i][k]+f[k][j]){
f[i][j]=f[i][k]+f[k][j];
}
}
}
}
}

但是本题还要求输出方案，所以我们考虑用vector来维护方案，每次更新ans时顺带更新方案。方案可以利用递归的方法求解：即利用Floyd的特性，将任意i,j之间最短路径的中转点存储在pos数组中，不断递归。

复制代码

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
typedef long long ll;
int n,m;
int f[N][N],a[N][N],pos[N][N],ans=INF;
vector<int> path;
void dfs(int i,int j){//表示获取i,j之间的路径上的所有节点（不包括i,j）
int k=pos[i][j];
if(!k) return;
dfs(i,k);
path.push_back(k);
dfs(k,j);
}
void Get_path(int i,int j,int k){
path.clear();//清空原有答案
path.push_back(k);
path.push_back(i);
dfs(i,j);
path.push_back(j);
}
void Floyd(){
memcpy(f,a,sizeof a);
for(int k=1;k<=n;k++){
for(int i=1;i<k;i++){
for(int j=i+1;j<k;j++){
if(ans>(ll)f[i][j]+a[i][k]+a[k][j]){
ans=f[i][j]+a[i][k]+a[k][j];
Get_path(i,j,k);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(f[i][j]>f[i][k]+f[k][j]){
f[i][j]=f[i][k]+f[k][j];
pos[i][j]=k;
}
}
}
}
}

这个算法的复杂度在最坏情况下是 $oleft ( n^{4} right )$ ，但是显然不可能达到这么大，一般情况下稳定在 $oleft ( n^{3} right )$ 。

例题6：牛站

二、最小生成树

1.基础知识

a.基本结论：最小生成树一定包含全图中边权最小的边。

b.推论：见蓝书P363。

c.Kruskal算法：基于推论（贪心），用于稀疏图，复杂度 $oleft ( mlogn right )$ 。

d.Prim算法：基于推论，用于稠密图尤其是完全图，复杂度 $oleft ( n^{2} right )$ 。

2.例题

例题1：AcWing 346.走廊泼水节（Kruskal算法）

这题要求我们将一棵树扩充成一个完全图，并且使得该图的最小生成树仍是这棵树。那么逆向思考：如果我们对一个完全图做Kruskal，发现每次选出最小的边开始合并时，两点各自所属的集合中都两两有边相连，而选择的这条边正是这所有边中严格最小的那条。所以我们可以想到大致的思路：对于树做一遍Kruskal，设选出的边所连的端点分别为x，y，边权为z。它们所处集合内的点数为num[x]与num[y]。那么一共可连(num[x]*num[y]-1)条边，每一条的边权都至少为z+1。可直接令答案加上(num[x]*num[y]-1)*(z+1)即可。

上述的num数组可以用并查集来维护，可参考下面的模板：AcWing 837.连通块中点的数量

复制代码

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<iostream>
#include<algorithm>
using namespace std;
const int N=6005;
typedef long long ll;
struct Node{
int x,y,z;
}edge[N];
bool cmp(Node a,Node b){
return a.z<b.z;
}
int fa[N],siz[N];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
int main(){
int T;
cin>>T;
while(T--){
int n;
cin>>n;
for(int i=1;i<n;i++){
int x,y,z;
cin>>x>>y>>z;
edge[i]={x,y,z};
}
for(int i=1;i<=n;i++){
fa[i]=i;
siz[i]=1;
}
sort(edge+1,edge+n,cmp);
ll ans=0;
for(int i=1;i<n;i++){
int a=find(edge[i].x),b=find(edge[i].y);
if(a!=b){
fa[a]=b;
ans+=(siz[a]*siz[b]-1)*(edge[i].z+1);
siz[b]+=siz[a];
}
}
cout<<ans<<endl;
}
}

例题2：野餐规划

例题3：AcWing 348.沙漠之王（Prim算法）

这题其实是个裸的0/1分数规划模型（见蓝书P185）。也就是说我们只要用二分答案计算即可。但是这里给的不是图，而是一堆在坐标系上的点。因此所有的点之间都要连一条边，自行计算边权。这样是一个完全图的问题。如果用Kruskal算法，时间复杂度为 $oleft ( n^{2}logn right )$ ，算上二分的时间，已经超出了2s的限制。所以我们要采用Prim算法来提高效率。最终代码如下：

复制代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=1005;
const double eps=1e-6;
int n,m;
struct Poi{
int x,y;
double z;
}point[N];
struct Node{
double a,b;
}g[N][N];
double dist(int x1,int y1,int x2,int y2){
return (double)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double d[N];
bool st[N];
bool Prim(double mid){
memset(st,false,sizeof st);
double res=0;
for(int i=1;i<=n;i++) d[i]=1e9;
d[1]=0;
for(int i=1;i<n;i++){
int x=0;
for(int j=1;j<=n;j++){
if(!st[j] && (x==0 || d[x]>d[j])) x=j;
}
st[x]=true;
for(int y=1;y<=n;y++){
if(!st[y]) d[y]=min(d[y],g[x][y].a-mid*g[x][y].b);
}
}
for(int i=2;i<=n;i++) res+=d[i];
return res>=0;
}
int main(){
while(scanf("%d",&n) && n){
for(int i=1;i<=n;i++){
int x,y;
double z;
cin>>x>>y>>z;
point[i]={x,y,z};
}
m=0;
double l=1e9,r=-1e9;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
g[i][j]=g[j][i]={abs(point[i].z-point[j].z),dist(point[i].x,point[i].y,point[j].x,point[j].y)};
l=min(l,g[i][j].a/g[i][j].b);
r=max(r,g[i][j].a/g[i][j].b);
}
}
while(r-l>eps){
double mid=(l+r)/2;
if(Prim(mid)) l=mid;
else r=mid;
}
printf("%.3lfn",l);
}
return 0;
}

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=1005;
const double eps=1e-6;
int n,m;
struct Poi{
int x,y;
double z;
}point[N];
struct Node{
double a,b;
}g[N][N];
double dist(int x1,int y1,int x2,int y2){
return (double)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double d[N];
bool st[N];
bool Prim(double mid){
memset(st,false,sizeof st);
double res=0;
for(int i=1;i<=n;i++) d[i]=1e9;
d[1]=0;
for(int i=1;i<n;i++){
int x=0;
for(int j=1;j<=n;j++){
if(!st[j] && (x==0 || d[x]>d[j])) x=j;
}
st[x]=true;
for(int y=1;y<=n;y++){
if(!st[y]) d[y]=min(d[y],g[x][y].a-mid*g[x][y].b);
}
}
for(int i=2;i<=n;i++) res+=d[i];
return res>=0;
}
int main(){
while(scanf("%d",&n) && n){
for(int i=1;i<=n;i++){
int x,y;
double z;
cin>>x>>y>>z;
point[i]={x,y,z};
}
m=0;
double l=1e9,r=-1e9;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
g[i][j]=g[j][i]={abs(point[i].z-point[j].z),dist(point[i].x,point[i].y,point[j].x,point[j].y)};
l=min(l,g[i][j].a/g[i][j].b);
r=max(r,g[i][j].a/g[i][j].b);
}
}
while(r-l>eps){
double mid=(l+r)/2;
if(Prim(mid)) l=mid;
else r=mid;
}
printf("%.3lfn",l);
}
return 0;
}

例题4：AcWing 349.黑暗城堡（朴素Dijkstra算法+树形结构）

这题是要求一个无向图的以1为根的最短路径树的可能存在数量。

很明显，在最短路径树中，对于任意一对父子节点(x,y)，其中x为父节点，y为子节点，必然有dist[x]=dist[y]+w[x][y]。那么只要先求一遍dij，再对每一个点检查有多少个其它的点满足上述条件，最后相乘即可。书上说要对dist数组进行排序（保证父节点在前），其实不必。

其实我们可以得出一个结论：对任意的图求完最短路后，所有点到起点的最短路径会构成一棵树，这棵树就是最短路径树。

但是感觉这个题跟最小生成树关系不大啊，感觉更接近于最短路问题，或许是用到了树形结构也算是？

这题的图跟上题一样，属于稠密图，所以考虑使用朴素的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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n,m;
const int N=1005,mod=(ll)(1<<31)-1;
int g[N][N],cnt[N];
bool st[N];
ll dist[N];
priority_queue<PII,vector<PII>,greater<PII> > heap;
void dij(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=1;i<=n;i++){
int t=0;
for(int j=1;j<=n;j++){
if(!st[j] && (t==0 || dist[j]<dist[t])) t=j;
}
st[t]=true;
for(int j=1;j<=n;j++){
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
}
}
int main(){
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof g);
while(m--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
g[x][y]=g[y][x]=min(g[x][y],z);
}
dij();
for(int i=2;i<=n;i++){
for(int j=1;j<=n;j++){
if(dist[i]==dist[j]+g[j][i]){
cnt[i]++;
}
}
}
ll ans=1;
for(int i=2;i<=n;i++){
if(cnt[i]) ans=ans*cnt[i]%mod;//可以处理到不了的情况
}
printf("%lld",ans%mod);
}

练习1 ：AcWing 383.观光

这题是次短路及其条数的求法的模板题。容易证明：次短路的更新满足拓扑序，不会被环形更新（正数权值的影响），所以同最短路一样可以用Dijkstra算法来做。那么这题仿照之前bfs中用到的一个算法思想：拆点。即把同一个点拆为最短路点和次短路点。至于统计路径条数，可以参考最短路计数问题。代码如下：

复制代码

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e3+5,M=1e4+5,INF=0x3f3f3f3f;
int head[N],to[M],ne[M],w[M],idx;
int cnt[N][2],dist[N][2];
void add(int x,int y,int z){
ne[++idx]=head[x];
to[idx]=y;
w[idx]=z;
head[x]=idx;
}
bool st[N][2];
struct Node{
int ver,type,d;
bool operator> (const Node &W) const
{
return d>W.d;
}
};
priority_queue<Node,vector<Node>,greater<Node> > heap;
void dijkstra(int s){
memset(cnt,0,sizeof cnt);
memset(dist,0x3f,sizeof dist);
memset(st,false,sizeof st);
dist[s][0]=0;//0表示最短，1表示次短
cnt[s][0]=1;
heap.push({s,0,0});
while(heap.size()){
Node t=heap.top();
heap.pop();
if(st[t.ver][t.type]) continue;
st[t.ver][t.type]=true;
int count=cnt[t.ver][t.type];
for(int i=head[t.ver];i;i=ne[i]){
int j=to[i];
if(dist[j][0]>t.d+w[i]){
dist[j][1]=dist[j][0];cnt[j][1]=cnt[j][0];
heap.push({j,1,dist[j][1]});
dist[j][0]=t.d+w[i];cnt[j][0]=count;
heap.push({j,0,dist[j][0]});
}
else if(dist[j][0]==t.d+w[i]){
cnt[j][0]+=count;
}
else if(dist[j][1]>t.d+w[i]){
dist[j][1]=t.d+w[i];cnt[j][1]=count;
heap.push({j,1,dist[j][1]});
}
else if(dist[j][1]==t.d+w[i]){
cnt[j][1]+=count;
}
}
}
}
int main(){
int T;
cin>>T;
while(T--){
memset(head,0,sizeof head);
idx=0;
int n,m;
cin>>n>>m;
while(m--){
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
}
int s,f,res=0;
cin>>s>>f;
dijkstra(s);
res=cnt[f][0];
if(dist[f][1]-dist[f][0]==1) res+=cnt[f][1];
cout<<res<<endl;
}
}

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
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e3+5,M=1e4+5,INF=0x3f3f3f3f;
int head[N],to[M],ne[M],w[M],idx;
int cnt[N][2],dist[N][2];
void add(int x,int y,int z){
ne[++idx]=head[x];
to[idx]=y;
w[idx]=z;
head[x]=idx;
}
bool st[N][2];
struct Node{
int ver,type,d;
bool operator> (const Node &W) const
{
return d>W.d;
}
};
priority_queue<Node,vector<Node>,greater<Node> > heap;
void dijkstra(int s){
memset(cnt,0,sizeof cnt);
memset(dist,0x3f,sizeof dist);
memset(st,false,sizeof st);
dist[s][0]=0;//0表示最短，1表示次短
cnt[s][0]=1;
heap.push({s,0,0});
while(heap.size()){
Node t=heap.top();
heap.pop();
if(st[t.ver][t.type]) continue;
st[t.ver][t.type]=true;
int count=cnt[t.ver][t.type];
for(int i=head[t.ver];i;i=ne[i]){
int j=to[i];
if(dist[j][0]>t.d+w[i]){
dist[j][1]=dist[j][0];cnt[j][1]=cnt[j][0];
heap.push({j,1,dist[j][1]});
dist[j][0]=t.d+w[i];cnt[j][0]=count;
heap.push({j,0,dist[j][0]});
}
else if(dist[j][0]==t.d+w[i]){
cnt[j][0]+=count;
}
else if(dist[j][1]>t.d+w[i]){
dist[j][1]=t.d+w[i];cnt[j][1]=count;
heap.push({j,1,dist[j][1]});
}
else if(dist[j][1]==t.d+w[i]){
cnt[j][1]+=count;
}
}
}
}
int main(){
int T;
cin>>T;
while(T--){
memset(head,0,sizeof head);
idx=0;
int n,m;
cin>>n>>m;
while(m--){
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
}
int s,f,res=0;
cin>>s>>f;
dijkstra(s);
res=cnt[f][0];
if(dist[f][1]-dist[f][0]==1) res+=cnt[f][1];
cout<<res<<endl;
}
}

最后

以上就是粗暴芝麻最近收集整理的关于图论基础之最短路和最小生成树一、最短路二、最小生成树的全部内容，更多相关图论基础之最短路和最小生成树一、最短路二、最小生成树内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：笔记
浏览次数：98 次浏览
发布日期：2023-11-18 12:45:04
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_o_14_f3_13_jk1.html

图论基础之最短路和最小生成树一、最短路二、最小生成树

一、最短路

1.基础知识

2.例题

例题1：AcWing 340.通信线路(堆优化的Dijkstra算法)

例题2:AcWing 341.最优贸易(SPFA算法)

例题3：AcWing 342.道路与航线(最短路在图论问题中的综合应用)

例题4：AcWing 343.排序(Floyd解决传递闭包问题)

例题5：AcWing 344.观光之旅（Floyd求最小环）

二、最小生成树

1.基础知识

2.例题

例题1：AcWing 346.走廊泼水节（Kruskal算法）

例题3：AcWing 348.沙漠之王（Prim算法）

例题4：AcWing 349.黑暗城堡（朴素Dijkstra算法+树形结构）

最后

评论列表共有 0 条评论

发表评论取消回复

图论基础之最短路和最小生成树一、最短路二、最小生成树

一、最短路

1.基础知识

2.例题

例题1：AcWing 340.通信线路(堆优化的Dijkstra算法)

例题2:AcWing 341.最优贸易(SPFA算法)

例题3：AcWing 342.道路与航线(最短路在图论问题中的综合应用)

例题4：AcWing 343.排序(Floyd解决传递闭包问题)

例题5：AcWing 344.观光之旅（Floyd求最小环）

二、最小生成树

1.基础知识

2.例题

例题1：AcWing 346.走廊泼水节（Kruskal算法）

例题3：AcWing 348.沙漠之王（Prim算法）

例题4：AcWing 349.黑暗城堡（朴素Dijkstra算法+树形结构）

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复