ACM算法模板：最小生成树与Prim实现详解

ACM竞赛模板

需积分: 9 70 浏览量更新于2024-07-20 收藏 192KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

本资源提供的是两个用于解决ACM（Association for Computing Machinery）竞赛中涉及的图论问题——最小生成树（Minimum Spanning Tree, MST）算法的C++代码模板。这里主要关注两种经典算法：Kruskal's Algorithm 和 Prim's Algorithm。 **1. Kruskal's Minimum Spanning Tree (Kruskal's Algorithm)** Kruskal's Algorithm 是一种贪心算法，用于寻找一个无向图的最小生成树。代码中定义了一个`edg`结构体来表示边，包含三个字段：起点`u`、终点`v`和权重`w`。`all_e`数组用于存储所有的边，其中`<`运算符重载用于按照边的权重进行排序。`uni`函数是并查集数据结构的实现，用于合并两个集合，如果两个顶点不在同一集合，则合并并更新集合大小。在主函数中，首先对所有边进行排序，然后遍历边，每次选择权重最小且不会形成环的新边，将其添加到最小生成树中，直到生成树包含n-1条边。 **2. Prim's Algorithm** Prim's Algorithm 是另一种求解最小生成树的算法，通常用于处理连通图。这个版本的代码没有给出完整的Prim算法实现，但从`set`数组和`g`邻接矩阵可以推测，它可能是用邻接矩阵表示图，其中`set`数组用于标记节点是否已被访问过，`str`数组可能用于存储节点的名称或字符串标识。`make_`函数部分缺失，但可以推断这部分可能用于构建邻接矩阵或者初始化其他辅助数据结构。Prim算法通常是从一个起点开始，逐步扩展生成树，每次添加与当前树中任意顶点相连且权重最小的新边。总结来说，这份代码提供了两种常用算法的基本框架，适合ACM竞赛中解决关于最小生成树的问题。理解并熟悉这两种算法的原理和实现方式对于参赛者来说至关重要，因为它们是解决这类问题的核心技术。同时，代码中的数据结构和函数设计也需要参赛者根据具体问题调整和优化。

资源详情

资源推荐

ACM 算法资料集锦 2017 年 4 月 26 日星期三

g[u].push_back(v);

}

scc(n,g,set);

int pi=1,ptosc[M];

struct Scc{

int p,n;

}sc[M];

memset(sc,0,sizeof(sc));

for(i=1;i<=n;i++){

int p=findp(set,i);

if(sc[p].p==0) {sc[p].p=pi; ptosc[pi++]=p;}

sc[p].n++;

}

int n2=pi-1,od[M];

memset(od,0,sizeof(od));

for(i=1;i<=n;i++){

for(j=0;j<g[i].size();j++){

u=findp(set,i); v=findp(set,g[i][j]);

if(sc[u].p!=sc[v].p) od[sc[u].p]++;

}

int sum=0,s1=0;

for(i=1;i<=n2;i++) if(od[i]==0) {s1++; sum+=sc[ptosc[i]].n;}

if(s1!=1) sum=0;

cout << sum << endl;

}

最大匹配

#include <iostream>

#include <string>

#include <math.h>

using namespace std;

#define M 1001

int n,m,match[M],ans[M];

bool visit[M],g[M][M];

//O(n^3)

bool dfs(int k,bool map[M][M]){

int t;

for(int i = 1; i <= m; i++){

if(map[k][i] && !visit[i]){

visit[i] = true;

t = match[i];

match[i] = k;

if(t == 0 || dfs(t,map))

return true;

match[i] = t;

}

return false;

}

int main(){

int i,sum=0,t,j,u,v;

cin >> t;

while(t--){

sum=0;

memset(match,0,sizeof(match));

memset(g,0,sizeof(g));

scanf("%d%d",&n,&m);

for(i=1;i<=m;i++){

scanf("%d%d",&u,&v);

g[u][v]=true;

}

m=n;

for(i=1;i<=n; i++){

memset(visit,0,sizeof(visit));

if(dfs(i,g)) sum++;

}

cout << n-sum << endl;

}

return 0;

}

还有两个最大匹配模板

#include <iostream>

#include <string>

#include <math.h>

#include <vector>

using namespace std;

#define M 3001

bool g[M][M];

int mk[M] ,cx[M],pred[M],open[M],cy[M],nx,ny;

//边少适用 O(n^3)

int MaxMatchBFS()

{

int i , u , v , t , d , e , cur , tail , res(0) ;

memset(mk , 0xff , sizeof(mk)) ;

memset(cx , 0xff , sizeof(cx)) ;

memset(cy , 0xff , sizeof(cy)) ;

for (i = 0 ; i < nx ; i++){

pred[i] = -1 ;

for (open[cur = tail = 0] = i ; cur <= tail && cx[i] == -1 ; cur+

+){

ACM 算法资料集锦 2017 年 4 月 26 日星期三

for (u = open[cur] , v = 0 ; v < ny && cx[i] == -1 ; v ++) if (g[u][v]

&& mk[v] != i)

{

mk[v] = i ; open[++tail] = cy[v] ; if (open[tail] >= 0)

{ pred[open[tail]] = u ; continue ; }

for (d = u , e = v ; d != -1 ; t = cx[d] , cx[d] = e , cy[e] = d , e = t ,

d = pred[d]) ;

}

if (cx[i] != -1) res++ ;

}

return res ;

}

int path(int u){

for (int v = 0 ; v < ny ; v++)

if (g[u][v] && !mk[v]){

mk[v] = 1 ;

if (cy[v] == -1 || path(cy[v])) {

cx[u] = v ;

cy[v] = u ;

return 1 ;

}

} return 0 ;

}

//少适用 O(n^3)

int MaxMatchDFS()

{

int res(0) ;

memset(cx , 0xff , sizeof(cx)) ;

memset(cy , 0xff , sizeof(cy)) ;

for (int i = 0 ; i < nx ; i++)

if (cx[i] == -1){

memset(mk , 0 , sizeof(mk));

res += path(i) ;

}

return res ;

}

最大权匹配,KM 算法

//此 KM 算法，坐标从 1 开始，记住

#include <iostream>

#include <vector>

#include <math.h>

using namespace std;

#define M 110

int n; // X 的大小

int lx[M], ly[M]; // 标号

bool sx[M], sy[M]; // 是否被搜索过

int match[M]; // Y(i) 与 X(match [i]) 匹配

// 从 X(u) 寻找增广道路，找到则返回 true

bool path(int u,int weight[M][M]) {

sx [u] = true;

for (int v = 0; v < n; v ++)

if (!sy [v] && lx[u] + ly [v] == weight [u] [v]) {

sy [v] = true;

if (match [v] == -1 || path(match [v],weight)) {

match [v] = u;

return true;

}

return false;

}

// 参数 Msum 为 true ，返回最大权匹配，否则最小权匹配

int km(bool Msum,int weight[M][M]) {

int i, j;

if (!Msum) {

for (i = 0; i < n; i ++)

for (j = 0; j < n; j ++)

weight [i] [j] = -weight [i] [j];

}

// 初始化标号

for (i = 0; i < n; i ++) {

lx [i] = -0x1FFFFFFF;

ly [i] = 0;

for (j = 0; j < n; j ++)

if (lx [i] < weight [i] [j])

lx [i] = weight [i] [j];

}

memset(match, -1, sizeof (match));

for (int u = 0; u < n; u ++)

while (1) {

memset(sx, 0, sizeof (sx));

memset(sy, 0, sizeof (sy));

if (path(u,weight))

break;

// 修改标号

int dx = 0x7FFFFFFF;

for (i = 0; i < n; i ++)

if (sx [i])

for (j = 0; j < n; j ++)

if(!sy [j])

剩余25页未读，继续阅读

享受编程.

粉丝: 63
资源: 2

ACM算法模板：最小生成树与Prim实现详解

ACM计算几何模板

经典计算几何模版

南京邮电大学ACM计算几何

acm模板整理和使用方法

ACM-ICPC模板整理

ACM算法自学推荐书目

上海交通大学acm 模板

acm常用java算法,java算法之「字符串反转」noip算法 ACM算法

中山大学acm模板.pdf

上海交通大学 acm模板

acm经典c语言算法代码

没学过acm可以搞算法吗

acm常用java算法,

请通过acm分析如何解决主人公的问题

acm竞赛常用算法与数据结构

acm六边形旋转连线通关算法

要想拿acm铜牌，要怎么学习算法

请列出打acm所需要学习的所有算法

ACM八球胜负问题的算法

acm codebooke

最新资源