没有合适的资源？快使用搜索试试~ 我知道了~

首页浙大ACM模板详解：核心技术与实例涵盖数论、图论与网络流

浙大ACM模板详解：核心技术与实例涵盖数论、图论与网络流

5星 · 超过95%的资源需积分: 13 15 下载量 191 浏览量更新于2024-07-27 收藏 441KB DOC 举报

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

30元优惠券

试读

64页

"浙江大学ACM模板是一个专为计算机算法竞赛设计的实用工具，尤其针对在ACM（国际大学生程序设计竞赛）中常见的数论、图论和网络流问题提供了解题模板。这个模板覆盖了多个关键知识点，旨在帮助学生提高编程效率和解题策略。在数论部分，它包含了基础且重要的概念，如阶乘最后非零位的计算方法、模线性方程组的求解、素数表的构建、素数的随机判断（Miller-Rabin测试）、质因数分解以及欧几里得最大公约数和欧拉函数的求解。这些内容是算法设计中必不可少的数论工具。图论部分则涵盖了多个匹配问题的解决方案，如二分图的最大匹配（使用Hungarian算法的不同实现方式，包括邻接表、邻接矩阵两种数据结构），以及一般图的匹配。此外，还有生成树的构建，如Kruskal算法和Prim算法的邻接表和正向表版本，以及最小生成树的多种实现形式。网络流部分涉及上下界最大流和最小流的计算，以及最大流（包括带权和无权）、最小费用最大流等经典问题。这些算法在处理实际网络问题时具有广泛的应用。最短路径部分则是通过Dijkstra算法的多种实现，如BFS和二叉堆、映射堆等数据结构的使用，解决了单源和多源最短路径的问题。这些算法在实时路径规划和路由优化中至关重要。浙大ACM模板提供了一个全面的框架，不仅有利于学生们理解和掌握基础算法，还能让他们在实战竞赛中快速定位问题并编写出高效的代码。无论是对于提升算法技能，还是准备ACM比赛，都是极具价值的学习资料。"

资源详情

资源推荐

int hungary(int m,int n,int mat[][MAXN],int* match1,int* match2){

int s[MAXN],t[MAXN],p,q,ret=0,i,j,k;

for (_clr(match1),_clr(match2),i=0;i<m;ret+=(match1[i++]>=0))

for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)

for (k=s[p],j=0;j<n&&match1[i]<0;j++)

if (mat[k][j]&&t[j]<0){

s[++q]=match2[j],t[j]=k;

if (s[q]<0)

for (p=j;p>=0;j=p)

match2[j]=k=t[j],p=match1[k],match1[k]=j;

}

return ret;

}

4. 二分图最大匹配(hungary 正向表形式)

//二分图最大匹配,hungary 算法,正向表形式,复杂度 O(m*e)

//返回最大匹配数,传入二分图大小 m,n 和正向表 list,buf(只需一边)

//match1,match2 返回一个最大匹配,未匹配顶点 match 值为-1

#include <string.h>

#define MAXN 310

#define _clr(x) memset(x,0xff,sizeof(int)*MAXN)

int hungary(int m,int n,int* list,int* buf,int* match1,int* match2){

int s[MAXN],t[MAXN],p,q,ret=0,i,j,k,l;

for (_clr(match1),_clr(match2),i=0;i<m;ret+=(match1[i++]>=0))

for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)

for (l=list[k=s[p]];l<list[k+1]&&match1[i]<0;l++)

if (t[j=buf[l]]<0){

s[++q]=match2[j],t[j]=k;

if (s[q]<0)

for (p=j;p>=0;j=p)

match2[j]=k=t[j],p=match1[k],match1[k]=j;

}

return ret;

}

5. 二分图最佳匹配(kuhn_munkras 邻接阵形式)

//二分图最佳匹配,kuhn munkras 算法,邻接阵形式,复杂度 O(m*m*n)

//返回最佳匹配值,传入二分图大小 m,n 和邻接阵 mat,表示权值

//match1,match2 返回一个最佳匹配,未匹配顶点 match 值为-1

//一定注意 m<=n,否则循环无法终止

//最小权匹配可将权值取相反数

#include <string.h>

#define MAXN 310

#define inf 1000000000

#define _clr(x) memset(x,0xff,sizeof(int)*n)

int kuhn_munkras(int m,int n,int mat[][MAXN],int* match1,int* match2){

int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN],p,q,ret=0,i,j,k;

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

for (l1[i]=-inf,j=0;j<n;j++)

l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];

for (i=0;i<n;l2[i++]=0);

for (_clr(match1),_clr(match2),i=0;i<m;i++){

for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)

for (k=s[p],j=0;j<n&&match1[i]<0;j++)

if (l1[k]+l2[j]==mat[k][j]&&t[j]<0){

s[++q]=match2[j],t[j]=k;

if (s[q]<0)

for (p=j;p>=0;j=p)

match2[j]=k=t[j],p=match1[k],match1[k]=j;

}

if (match1[i]<0){

for (i--,p=inf,k=0;k<=q;k++)

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

if (t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j]<p)

p=l1[s[k]]+l2[j]-mat[s[k]][j];

for (j=0;j<n;l2[j]+=t[j]<0?0:p,j++);

for (k=0;k<=q;l1[s[k++]]-=p);

}

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

ret+=mat[i][match1[i]];

return ret;

}

6. 一般图匹配(邻接表形式)

//一般图最大匹配,邻接表形式,复杂度 O(n*e)

//返回匹配顶点对数,match 返回匹配,未匹配顶点 match 值为-1

//传入图的顶点数 n 和邻接表 list

#define MAXN 100

struct edge_t{

int from,to;

edge_t* next;

};

int aug(int n,edge_t* list[],int* match,int* v,int now){

int t,ret=0;edge_t* e;

v[now]=1;

for (e=list[now];e;e=e->next)

if (!v[t=e->to]){

if (match[t]<0)

match[now]=t,match[t]=now,ret=1;

else{

v[t]=1;

if (aug(n,list,match,v,match[t]))

match[now]=t,match[t]=now,ret=1;

v[t]=0;

}

if (ret)

break;

}

v[now]=0;

return ret;

}

int graph_match(int n,edge_t* list[],int* match){

int v[MAXN],i,j;

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

v[i]=0,match[i]=-1;

for (i=0,j=n;i<n&&j>=2;)

if (match[i]<0&&aug(n,list,match,v,i))

i=0,j-=2;

else

i++;

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

j+=(match[i]>=0);

return j/2;

}

7. 一般图匹配(邻接表形式,邻接阵接口)

//一般图最大匹配,邻接表形式,复杂度 O(n*e)

//返回匹配顶点对数,match 返回匹配,未匹配顶点 match 值为-1

//传入图的顶点数 n 和邻接表 list

#include <vector>

#define MAXN 100

int aug(int n,vector<int> list[],int* match,int* v,int now){

剩余63页未读，继续阅读

粉丝: 456
资源: 8

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

浙大ACM模板详解：核心技术与实例涵盖数论、图论与网络流

浙江大学ACM模板

浙江大学ACM模板(经典代码）

浙江大学 ACM 模板

上海交通大学acm 模板

中山大学acm模板.pdf

上海交通大学 acm模板

acm模板整理和使用方法

ACM-ICPC模板整理

ACM线段树模板C++

latex 子图片 acm

acm期刊word模版

linux cdc acm配置

acm程序设计 pdf

北京大学acm1953

Bridge（acm）

acm竞赛题目pdf

python ACM树结构

河南省acm历年真题

usb uvc + acm descriptor

山东省2018acm试题

最新资源