ACM算法集：最小生成树与Prim算法详解

需积分: 0 77 浏览量更新于2024-07-28 1 收藏 292KB DOC 举报

"ACM经典算法集锦"是一份涵盖了在算法竞赛中常见的ACM算法精选文档，着重于解决实际问题中的最小生成树和最短路径问题。该文档提供了一些示例代码，展示了如何使用C++实现Prim算法和Kruskal算法来求解这些问题。首先，我们来看看Kruskal最小生成树算法。Kruskal算法的核心是贪心策略，通过合并边来构建一棵树，直到树的边集包含所有顶点。在这个C++实现中： 1. 定义了一个`edg`结构体，包含了边的起点`u`、终点`v`和权重`w`。 2. `operator<`函数用于比较边的权重，决定边的顺序。 3. `uni`函数实现了并查集数据结构，用于查找两个顶点是否属于同一个集合。如果它们属于不同的集合，将较小集合合并到较大集合中。 4. `main`函数中，首先读入测试用例数量`t`，然后输入图的节点数量`n`和边的信息。所有边按照权重排序后，使用`uni`函数依次合并边，每次找到一条形成新最小生成树的新边，直到形成一棵包含所有顶点的树。 5. 最后输出生成树中最大的边（即最小权重）的权重。接着是Prim算法，也用于求解最小生成树，但它的策略是每次从已选择的顶点中选择一个未被连接的顶点，与当前最小生成树中最远的顶点相连。这里没有给出完整的Prim算法实现，但可以推测实现中会有以下部分： 1. 初始化一个集合`set`表示已选择的顶点，以及一个邻接矩阵`g`存储边的信息。 2. 一个循环中，遍历未选择的顶点，计算与已选择顶点间的最小边，将这条边的另一端加入集合`set`，并更新邻接矩阵。 3. 当所有顶点都被选择或者没有新的边可以添加时，最小生成树构建完成，输出树的总权重。这些算法在ACM竞赛中经常被用来处理图论问题，如寻找网络中连接所有节点的最低成本路径或构建最小代价的连通结构。理解并熟练掌握这两种算法对于提高在ACM这类编程竞赛中的竞争力至关重要。同时，熟悉并能够优化这类基础算法也是提升算法设计和分析能力的关键步骤。

ACM 算法资料集锦 2009 年 12 月 10 日星期四

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 算法资料集锦 2009 年 12 月 10 日星期四

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页未读，继续阅读

kscbetrue

粉丝: 0
资源: 6

ACM算法集：最小生成树与Prim算法详解

ACM超级经典算法大集合

ACM经典算法及例子

ACM经典算法（对初学者很有用）

acm经典c语言算法代码

ACM算法自学推荐书目

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

没学过acm可以搞算法吗

acm常用java算法,

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

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

最新资源