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

最小生成树

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

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

Prim算法

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

模板

#includeusing 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]>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…

#includeusing namespace std;using ll=long long;#define INF 1e9int 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>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;jcal(p[k],p[j])){dis[j]=cal(p[k],p[j]);}}} printf(\"%.2lf\\n\",ans);return 0;} 

Kruskal算法

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

模板

#include#include#include#include#include#include #includeusing 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 买礼物 - 洛谷

引入虚假的点来转化点权

#includeusing 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>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>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;}