最小生成树与单源最短路径
最小生成树与单源最短路径
prim和dijkstra大同小异,唯一的区别是prim是维护树到其余节点的最小路径,而dijkstra是维护源节点到各个节点的最小路径。
例题:- 计算机软件能力认证考试系统 ccf201812-4
kruskal模板
/*
Kruskal算法求MST
*/
#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<fstream>
using namespace std;
const int MAXN=1000000;//最大点数
const int MAXM=1000000;//最大边数
int F[MAXN];//并查集使用 查找使用的,可以改为用set来记录在A中的结点(相关概念见算法导论)
struct Edge
{
int u,v,w;
}edge[MAXM];//储存边的信息,包括起点/终点/权值
int tol;//边数,加边前赋值为0
void addedge(int u,int v,int w)
{
edge[tol].u=u;
edge[tol].v=v;
edge[tol++].w=w;
}
bool cmp(Edge a,Edge b)//排序函数,边按照权值从小到大排序
{
return a.w<b.w;
}
int Find(int x)
{
if(F[x]==-1)
return x;
else
return F[x]=Find(F[x]);//平均时间复杂度为常数级
}
int Kruskal(int n)//传入点数,返回最小生成树的权值,如果不连通返回-1
{
memset(F,-1,sizeof(F));
sort(edge,edge+tol,cmp);
int cnt=0;//计算加入的边数
int ans=0,maxedge = 0;
for(int i=0;i<tol;i++)
{
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
int t1=Find(u);
int t2=Find(v);
if(t1!=t2)
{
ans+=w;
maxedge = max(maxedge,w);
F[t1]=t2;
cnt++;
}
if(cnt==n-1)//当添加的边数已经为n-1(n为结点数)时表示最小生成树已形成
break;
}
if(cnt<n-1)
return -1;//不连通
else
return maxedge;
}
int main( )
{
int N,m,root;
cin >> N;
cin >> m;
cin >> root;
for(int i = 0; i < m;i++)
{
int u,v,w;
cin >> u >> v >> w;
addedge(u,v,w);
}
cout<<Kruskal(N)<<endl;
return 0;
}
prim模板
const int INF=0x3f3f3f3f;
const int maxn=1200;
int dist[maxn],g[maxn][maxn],N;// dist[i]表示源结点到i的最小距离,g[i][j]表示图中结点i到j的路径代价
bool vis[maxn];
void dijkstra()
{
for(int i=1;i<=N;i++)
dist[i]=(i==1)?0:INF;// 初始化,以i = 1 作为源结点
memset(vis,0,sizeof(vis));
for(int i=1;i<=N;i++)
{
int mark=-1,mindis=INF;
for(int j=1;j<=N;j++)
{
if(!vis[j]&&dist[j]<mindis)
{
mindis=dist[j];
mark=j;
}
}
vis[mark]=1;
for(int j=1;j<=N;j++)
{
if(!vis[j])
{
dist[j]=min(dist[j],g[mark][j]);//prim,求最小生成树
//dist[j]=min(dist[j],dist[mark]+g[mark][j]);//dijkstra,求单源最短路径
}
}
}
}
内存优化(但是时间复杂度高,70分):
#include <iostream>
#include<string.h>
#include<vector>
#include<map>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxN = 50010;//最大节点数
int dist[maxN], point[maxN], n, m;
bool vis[maxN];
std::vector<pair<int, int> > g[maxN];//g[i][j] = <fi, se> 为边(i , fi)的距离se;
void dijkstra(int root)
{
for(int i=1;i<=n;i++)
dist[i]=(i==root)?0:INF;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
{
int mark=-1,mindis=INF;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&dist[j]<mindis)
{
mindis=dist[j];
mark=j;
}
}
vis[mark]=1;
for(int j=0;j<g[mark].size();j++)
{
if(!vis[g[mark][j].first])
{
//dist[g[mark][j].fi]=min(dist[g[mark][j].fi],dist[mark]+g[mark][j].se);
int temax = max(dist[mark],g[mark][j].second);
dist[g[mark][j].first] = min(dist[g[mark][j].first],temax);
}
}
}
}
int main()
{
int m,root;
cin >> n;
cin >> m;
cin >> root;
for(int i = 0; i < m;i++)
{
int u,v,w;
cin >> u >> v >> w;
g[u].push_back(make_pair(v,w));
g[v].push_back(make_pair(u,w));
}
dijkstra(root);
int ans = 0;
for(int i = 1; i <= n;i++)
{
if(dist[i] != INF)
{
ans = max(ans,dist[i]);
}
}
cout << ans <<endl;
return 0;
}
堆优化(100分):
#include <iostream>
#include<string.h>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<queue>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<int,int> pir;
//#define mem(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f;
const int maxN = 50010;//最大节点数
const int maxM = 1000000;//最大边数
int first[maxN],tot;
int vis[maxN],dist[maxN],n,m;
priority_queue <pir,vector<pir>,greater<pir>> q;
/*存放的内容与dist相同,都是当前树到其余节点的最小值,但是该方式的优先队列的对头总是权值最小的*/
struct edge
{
int v,w,next;
}e[maxM*2];
void add_edge(int u,int v,int w)
{
e[tot].v=v;
e[tot].w=w;
e[tot].next=first[u];//first用来记录上一个从u出发的边在e中的下标
first[u]=tot++;
}
void init()
{
memset(first, -1,sizeof(first));
tot=0;
memset(dist, INF, sizeof(dist));
}
int prim(int root)
{
int cnt=0,sum=0,maxedge=0;
dist[root]=0;
q.push(make_pair(0,root));
while(!q.empty()&&cnt<n)
{
int d=q.top().first,u=q.top().second;
q.pop();
maxedge = max(maxedge, d);
if(!vis[u])
{
cnt++;
sum+=d;
vis[u]=1;
for(int i=first[u]; ~i; i=e[i].next)
if(e[i].w<dist[e[i].v])
{
dist[e[i].v]=e[i].w;
q.push(make_pair(dist[e[i].v],e[i].v));
}
}
}
return maxedge;
}
int main()
{
int u,v,w;
int root;
init();
scanf("%d%d%d",&n,&m,&root);
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
add_edge(v,u,w);
}
cout << prim(root) <<endl;
return 0;
}
ps:还缺一个prim加edge的模板
prim踩坑总结:
- 对于普通的prim解法(第一个),当数据规模较大时将不能一次申请那么多内存空间
- 所以需要内存优化,可以用vector<pair<int, int> > g[maxN]来存放边集,但不能用map,时间复杂度太高,经测试只能得20分。
- 即便内存优化完也只能得70分,部分测试点超时,所以需要堆优化,满分通过。