ACM入门必备：经典算法详解与实战练习

需积分: 3 59 浏览量更新于2024-07-22 5 收藏 292KB DOC 举报

本资源是一份针对ACM竞赛（Association for Computing Machinery）的算法锦集，特别适合初学者进行入门学习，重点介绍了两种经典的图论算法：Kruskal's Minimum Spanning Tree (Kruskal's MST) 和 Prim's Algorithm。这两种算法在比赛中经常被用于解决最短路径和最小生成树问题。 **Kruskal's Minimum Spanning Tree (Kruskal's MST)** Kruskal's算法是一种寻找无向图中最小生成树的贪心算法。它通过从小到大排序边的权重，每次选择当前未加入树中的最小权重边，并确保这条边不会形成环。代码中定义了一个`edg`结构体来存储边的起始顶点 `u`、结束顶点 `v` 和权重 `w`，并实现了一个自定义比较函数 `<` 来按照边的权重进行排序。`uni` 函数用于合并集合，判断添加新边后是否会形成环。在主函数中，读取输入的边和顶点数量，进行排序，然后逐步添加边到最小生成树，直到达到n-1个顶点连接。 **Prim's Algorithm** Prim's算法则是另一种寻找最小生成树的方法，它采用启发式策略，从一个初始顶点开始，每次添加与当前树相连的最短边。在这个版本的代码中，`set` 数组用来记录已经添加到最小生成树的顶点，`g` 数组表示图的邻接矩阵。`make_` 函数部分可能缺失了，但通常会用于构建邻接矩阵或处理字符串，以便在Prim's算法中处理图的邻接关系。主函数中，首先初始化集合和邻接矩阵，然后迭代添加边，直到所有顶点都被包含在内。总结来说，这份资源涵盖了ACM竞赛中常用的Kruskal's和Prim's算法的实现，对于想要提升解决图论问题能力的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页未读，继续阅读

tommyzht

粉丝: 42
资源: 3

ACM入门必备：经典算法详解与实战练习

ACM算法指南合集

ACM算法模板 · 一些常用的算法模板-模板合集

ACM 算法模板集

ACM 算法集--常用ACM算法

ACM+算法集--常用ACM算法

ACM试题锦集

ACM算法集集合

吉林大学ACM算法模板合集

ACM算法模板集：编程必备工具

ACM算法模板集：从基础到高级

最新资源