算法竞赛备赛——【图论】最小生成树

最小生成树

无向图 连通图才有最小生成树 可以判断图是否连通

记住思路 不要死记模板 灵活建图写代码

Prim算法

由Prim提出。该算法的基本思想是从一个结点开始，不断加点（而不是 Kruskal 算法的加边）。每次总是选出一个离生成树距离最小的点去加入生成树，最后实现最小生成树。类似Dijkstra算法。时间复杂度 O（V^2）------->稠密图

模板

#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
const int inf=0x7fffffff;
int cnt;
struct edge
{int u,w,next;
}e[2*maxn];
int head[maxn];
int dis[maxn];
bool vis[maxn];
int n,m;
void add(int x,int y,int w)		//链式前向星的加点方法
{cnt++;e[cnt].u=y;e[cnt].w=w;e[cnt].next=head[x];head[x]=cnt;
}
int prim()
{for(int i=1;i<=n;i++)dis[i]=inf;dis[1]=0;vis[1]=1;int now=1;for(int i=head[now];i;i=e[i].next)	//链式前向星的遍历方法   可利用堆优化{int u=e[i].u;dis[u]=min(dis[u],e[i].w);}int tot=0;int sum=0;while(tot<n-1){int mindis=inf;for(int i=1;i<=n;i++){if(!vis[i]&&dis[i]<mindis){now=i;mindis=dis[i];}}if(mindis==inf)return -1;//图不连通tot++;sum+=mindis;vis[now]=1;for(int i=head[now];i;i=e[i].next)	//链式前=前向星的遍历方法{int u=e[i].u;if(vis[u])continue;dis[u]=min(dis[u],e[i].w);}}return sum;
}
int main()
{cin>>n>>m;for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}int ans=prim();if(ans==-1)printf("orz");else printf("%d",ans);
}

例题

P1265 公路修建 - 洛谷

只能用Prim算法 边有5000*5000

完全图不用存图

设置变量不要用y1,y2,y3…

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define INF 1e9
int n;
struct node{int x,y;
}p[5005];
double dis[5005];
int v[5005];
double cal(const node& p1,const node& p2){return (double)sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(double)(p1.y-p2.y)*(p1.y-p2.y));//用double 
}int main(){cin>>n;for(int i=1;i<=n;++i){cin>>p[i].x>>p[i].y; }dis[1]=0;v[1]=1;for(int i=2;i<=n;i++){dis[i]=cal(p[1],p[i]);}double minn=INF,ans=0;int k;for(int i=1;i<n;++i){minn=INF;k=-1;for(int j=1;j<=n;++j){if(v[j]==0&&dis[j]<minn){k=j;minn=dis[j];}}v[k]=1;ans+=minn;for(int j=1;j<=n;++j){if(v[j]==0&&dis[j]>cal(p[k],p[j])){dis[j]=cal(p[k],p[j]);}}} printf("%.2lf\n",ans);return 0;
} 

Kruskal算法

Kruskal 算法：由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。在加入边时，需要通过 并查集 来判断该边的两个端点是否属于同一集合（树），避免形成 “环”。时间复杂度 O（ElogE）-----> 稀疏图

模板

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include <climits>
#include<utility>
using namespace std;
const int maxn = 110; // 最大顶点数
const int maxm = 10010; // 最大边数
struct Edge {// 使用结构体储存每一条边，便于排序int u, v, w; // 表示有一条 (u,v) 的无向边，边权为 w
} e[maxm+5];
int ecnt;// 用于边表计数
void addEdge(int u, int v, int w){ // 加入一条无向边++ecnt;e[ecnt].u = u;e[ecnt].v = v;e[ecnt].w = w;
}
int fa[maxn]; // 并查集相关
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]); // 路径压缩
}
int n,m; // 顶点数 边数 
bool cmp(const Edge &a, const Edge &b){return a.w < b.w;
}
int Kruskal() { // Kruskal 算法核心过程for (int i = 1; i <= n; i++) {fa[i] = i; // 初始化并查集}sort (e + 1, e + ecnt + 1, cmp);int sum = 0;for (int i = 1; i <= ecnt; i++) {int u = e[i].u;int v = e[i].v;u = find(u);v = find(v);if (u != v) {fa[u] = v;sum += e[i].w;}}return sum;
}
int main(){scanf("%d %d",&n,&m);int x,y,w;for (int i = 1; i <= m; i++) {scanf("%d %d %d", &x,&y,&w);addEdge(x, y, w);}int ans = Kruskal();printf("%d\n",ans);return 0;
}

例题

P1194 买礼物 - 洛谷

引入虚假的点来转化点权

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int a,b; 
struct Edge{int u,v,w;
}e[300000];
int fa[505];
int cnt;bool cmp(const Edge& x,const Edge& y){return x.w<y.w;
}int find(int x){if(x!=fa[x]) return fa[x]=find(fa[x]);return fa[x];
}int main(){cin>>a>>b;//引入虚假的物品0，买了0再买其他物品for(int i=1;i<=b;++i){e[++cnt].u=0;e[cnt].v=i;e[cnt].w=a;}int k;for(int i=1;i<=b;++i){for(int j=1;j<=b;++j){cin>>k;if(k!=0){e[++cnt].u=i;e[cnt].v=j;e[cnt].w=k;}}}sort(e+1,e+cnt+1,cmp);for(int i=0;i<=b;++i){fa[i]=i;}int x,y,fx,fy,ans=0;for(int i=1;i<=cnt;++i){x=e[i].u;y=e[i].v;fx=find(x);fy=find(y);if(fx!=fy){ans+=e[i].w;fa[fx]=fy;}}cout<<ans<<endl;return 0;
}