ACM算法代码库：从入门到精通

需积分: 10 100 浏览量更新于2024-07-28 收藏 645KB PDF 举报

"ACM算法代码库包含各种算法，如图论、网络、数据结构，适合编程初学者和研究者学习和参考。" ACM算法代码库是一个宝贵的资源，尤其对于那些刚开始接触编程竞赛或想要深入理解算法的初学者和研究者。这个库涵盖了多个关键领域的算法，包括图论、网络流和数据结构，这些是ACM/ICPC竞赛中常见的问题类型。在图论部分，你可以找到一系列关于图的操作和算法，例如： 1. DAG的深度优先搜索（DFS）标记，用于遍历无向图的结构。 2. 找桥算法，帮助识别图中的关键连接。 3. 无向图连通度计算，用于确定图的分块数量。 4. 最大团问题，通过动态规划和DFS寻找图中最大的完全子图。 5. 欧拉路径算法，用于找出起点到终点的所有边恰好被经过一次的路径。 6. Dijkstra算法的两种实现，包括基于数组的O(N^2)和基于优先队列的O(E*LOGE)。 7. Bellman-Ford算法，用于求解单源最短路径问题，即使存在负权边也能处理。 8. SPFA（Shortest Path Faster Algorithm），一种改进的Dijkstra算法，适用于有负权边的情况。 9. 第K短路问题，可以通过Dijkstra或A*算法进行优化。 10. Prim算法用于求最小生成树，确保连接所有节点的边总权重最小。 11. 次小生成树算法，解决可能存在多棵最小生成树的情况。 12. 最小生成森林问题，处理图中可能存在的多颗最小生成树。 13. 有向图最小树形图和Minimal Steiner Tree问题，用于在网络设计中找到最小成本的连接方案。 14. Tarjan算法用于识别图中的强连通分量。 15. 弦图的判断和Perfect Elimination点排列，对于解决特定类型的图问题非常有用。 16. 稳定婚姻问题，一个著名的组合优化问题，可以使用Gale-Shapley算法解决。 17. 拓扑排序，用于对有向无环图进行线性排序。 18. 无向图和有向图的连通分支查找，使用DFS或BFS实现。 19. 有向图的最小点基算法，用于减少图的复杂度。 20. Floyd算法求解最小环，以及2-SAT问题，这是布尔逻辑的一种应用。网络流部分涉及网络中的流分配问题，如： 1. 二分图匹配，包括匈牙利算法的DFS和BFS实现，以及Hopcroft-Carp算法。 2. Kuhn-Munkres算法，用于求解二分图的最佳匹配。 3. 无向图的最小割算法，用于确定网络中能最大化流量的切割。 4. 有上下界限制的最小（最大）流问题。 5. Dinic算法，一种高效的最大流算法，具有O(V^2*E)的时间复杂度。 6. HLPP（Hao-Lin-Peleg-Perlman）最大流算法，时间复杂度为O(V^3)。 7. 最小费用流问题，考虑了边上的成本，有O(V*E*F)和O(V^2*F)两种实现。 8. 最佳边割集和点割集问题，用于优化网络中的流分配。 9. 最小边割集和最小点割集，与网络的连通度有关。 10. 最小路径覆盖和最小点集覆盖问题，关注网络中的覆盖优化。在数据结构部分，该库还包含了： 1. 求解某天是星期几的问题，这通常涉及到日期处理和计算。 2. 左偏树的合并，其合并操作具有O(LOGN)的时间复杂度。 3. 树状数组，一种高效的数据结构，用于在线性时间内更新和查询区间和。这个代码库不仅提供了算法的实现，还包含了详细的题目描述，使得学习者能够更好地理解和应用这些算法。无论是为了参加ACM竞赛还是提升自己的编程能力，这个资源都是一个宝贵的工具。

ct--;

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

if (g[id][j]<INF){

s[ct].id=j;

s[ct].fi=fi+g[id][j];

s[ct++].gi=s[ct].fi+dist[j];

push_heap(s,s+ct);

}

return -1;

}

int main(){

while (scanf("%d%d%d",&n,&m,&x)!=EOF){

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

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

gr[i][j]=g[i][j]=INF;

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

int x,y,z;

scanf("%d%d%d",&x,&y,&z);

x--,y--;

g[x][y]<?=z;

gr[y][x]<?=z;

}

init();

printf("%d\n",solve());

}

return 0;

}

/*==================================================*\

| Prim 求 MST

| INIT: cost[][]耗费矩阵(inf为无穷大);

| CALL: prim(cost, n); 返回-1代表原图不连通;

\*==================================================*/

#define typec int // type of cost

const typec inf = 0x3f3f3f3f; // max of cost

int vis[V]; typec lowc[V];

typec prim(typec cost[][V], int n) // vertex: 0 ~ n-1

{

int i, j, p;

typec minc, res = 0;

memset(vis, 0, sizeof(vis));

vis[0] = 1;

for (i=1; i<n; i++) lowc[i] = cost[0][i];

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

minc = inf; p = -1;

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

if (0 == vis[j] && minc > lowc[j]) {

minc = lowc[j]; p = j;

}

if (inf == minc) return -1; // 原图不连通

res += minc; vis[p] = 1;

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

if (0 == vis[j] && lowc[j] > cost[p][j])

lowc[j] = cost[p][j];

}

return res;

}

/*==================================================*\

| 次小生成树 O(V^2)

\*==================================================*/

结论次小生成树可由最小生成树换一条边得到.

证明: 可以证明下面一个强一些的结论：

T是某一棵最小生成树，T0是任一棵异于T的树，通过变换T0 --> T1 -->

T2 --> ... --> Tn (T) 变成最小生成树.所谓的变换是，每次把T_i

中的

某条边换成T中的一条边, 而且树T_(i+1)的权小于等于T_i的权.

具体操作是：

step 1. 在T_i中任取一条不在T中的边u_v.

step 2. 把边u_v去掉，就剩下两个连通分量A和B，在T中，必有唯一的

边u'_v' 连结A和B.

step 3. 显然u'_v'的权比u_v小 ( 否则,u_v就应该在T中).把u'_v'

替换u_v即得树T_(i+1).

特别地：取Tn为任一棵次小生成树，T_(n-1) 也就是次小生成树且跟T

差一条边. 结论得证.

算法：只要充分利用以上结论, 即得V^2的算法. 具体如下：

step 1. 先用prim求出最小生成树T. 在prim的同时，用一个矩阵

max[u][v] 记录在T中连结任意两点u,v的唯一的路中权值最大的那条边的

权值. (注意这里). 这是很容易做到的，因为prim是每次增加一个结点s, 而

设已经标号了的结点集合为

W, 则W中所有的结点到s的路中的最大权值的边就

是当前加入的这条边. step 1 用时 O(V^2).

step 2. 枚举所有不在T中的边u_v, 加入边u_v替换权为max[u][v]的边.

不断更新求最小值，即次小生成树. step 2 用时 O(E).故总时间为O(V^2).

/*==================================================*\

| 最小生成森林问题(k 颗树)O(mlogm).

\*==================================================*/

数据结构：并查集算法：改进Kruskal

根据Kruskal算法思想，图中的生成树在连完第n-1条边前，都是一个最小生

成森林，每次贪心的选择两个不属于同一连通分量的树（如果连接一个连通分

量，因为不会减少块数，那么就是不合算的）且用最“便宜”的边连起来，连

接n-1次后就形成了一棵MST，n-2次就形成了一个两棵树的最小生成森林，

n-3，……，n-k此后就形成了k颗树的最小生成森林，就是题目要求求解的。

/*==================================================*\

| 有向图最小树形图

| INIT: eg置为边表; res置为0; cp[i]置为i;

| CALL: dirtree(root, nv, ne); res是结果;

\*==================================================*/

#define typec int // type of res

const typec inf = 0x3f3f3f3f; // max of res

typec res, dis[V];

int to[V], cp[V], tag[V];

struct Edge { int u, v; typec c; } eg[E];

int iroot(int i){

if (cp[i] == i) return i;

return cp[i] = iroot(cp[i]);

}

int dirtree(int root, int nv, int ne) // root: 树根

{ // vertex: 0 ~ n-1

int i, j, k, circle = 0;

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

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

for (i = 0; i < nv; ++i) dis[i] = inf;

for (j = 0; j < ne; ++j) {

i = iroot(eg[j].u); k = iroot(eg[j].v);

if (k != i && dis[k] > eg[j].c) {

dis[k] = eg[j].c;

to[k] = i;

}

to[root] = -1; dis[root] = 0; tag[root] = root;

for (i = 0; i < nv; ++i) if (cp[i] == i && -1 == tag[i]){

j = i;

for ( ; j != -1 && tag[j] == -1; j = to[j])

tag[j] = i;

if (j == -1) return 0;

if (tag[j] == i) {

circle = 1; tag[j] = -2;

for (k = to[j]; k != j; k = to[k]) tag[k] = -2;

}

if (circle) {

for (j = 0; j < ne; ++j) {

i = iroot(eg[j].u); k = iroot(eg[j].v);

if (k != i && tag[k] == -2) eg[j].c -= dis[k];

}

for (i = 0; i < nv; ++i) if (tag[i] == -2) {

res += dis[i]; tag[i] = 0;

for (j = to[i]; j != i; j = to[j]) {

res += dis[j]; cp[j] = i; tag[j] = 0;

}

if (0 == dirtree(root, nv, ne)) return 0;

} else {

for (i = 0; i < nv; ++i) if (cp[i] == i) res +=

dis[i];

}

return 1; // 若返回0代表原图不连通

}

/*==================================================*\

| Minimal Steiner Tree

| G(V, E), A是V的一个子集, 求至少包含A中所有点的最小子树.

| 时间复杂度: O(N^3 + N * 2^A * (2^A + N))

| INIT: d[][]距离矩阵; id[]置为集合A中点的标号;

| CALL: steiner(int n, int a);

| main()函数解决的题目: Ticket to Ride, NWERC 2006/2007

| 给4个点对(a1, b1) ... (a4, b4),

| 求min(sigma(dist[ai][bi])),其中重复的路段只能算一次

| 这题要找出一个steiner森林, 最后要对森林中树的个数进行枚举

\*==================================================*/

#define typec int // type of cost

const typec inf = 0x3f3f3f3f; // max of cost

int vis[V], id[A]; //id[]: A中点的标号

typec d[V][V], dp[1<<A][V];//dp[i][v]: 点v到点集i的最短距离

void steiner(int n, int a){

int i, j, k, mx, mk, top = (1 << a);

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

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

if (d[i][j] > d[i][k] + d[k][j])

d[i][j] = d[i][k] + d[k][j];

for (i = 0; i < a; i++) { // vertex: 0 ~ n-1

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

dp[1 << i][j] = d[j][ id[i] ];

}

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

if ( 0 == (i & (i - 1)) ) continue;

memset(vis, 0, sizeof(vis));

for (k = 0; k < n; k++) { // init

for (dp[i][k] = inf, j = 1; j < i; j++)

if ((i | j) == i &&

dp[i][k] > dp[j][k] + dp[i - j][k])

dp[i][k] = dp[j][k] + dp[i - j][k];

}

for (j = 0; mx = inf, j < n; j++) { // update

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

if (dp[i][k] <= mx && 0 == vis[k])

mx = dp[i][mk = k];

for (k = 0, vis[mk] = 1; k < n; k++)

if (dp[i][mk] > dp[i][k] + d[k][mk])

dp[i][mk] = dp[i][k] + d[k][mk];

}

int main(void){

int n, a = 8;

// TODO: read data;

steiner(n, a);

// enum to find the result

for (i = 0, b = inf; z = 0, i < 256; b>z ? b=z : b, i++)

for (j = 0; y = 0, j < 4; z += !!y * dp[y][x], j++)

for (k = 0; k < 8; k += 2)

if ((i >> k & 3) == j)

y += 3 << k, x = id[k];

// TODO: cout << b << endl;

return 0;

}

/*==================================================*\

| Tarjan 强连通分量

| INIT: vec[]为邻接表; stop, cnt, scnt置0; pre[]置-1;

| CALL: for(i=0; i<n; ++i) if(-1==pre[i]) tarjan(i, n);

\*==================================================*/

vector<int> vec[V];

int id[V], pre[V], low[V], s[V], stop, cnt, scnt;

void tarjan(int v, int n) // vertex: 0 ~ n-1

{

int t, minc = low[v] = pre[v] = cnt++;

vector<int>::iterator pv;

s[stop++] = v;

for (pv = vec[v].begin(); pv != vec[v].end(); ++pv) {

if(-1 == pre[*pv]) tarjan(*pv, n);

if(low[*pv] < minc) minc=low[*pv];

}

if(minc < low[v]) {

low[v] = minc; return;

}

do {

id[t = s[--stop]] = scnt; low[t] = n;

} while(t != v);

++scnt; // 强连通分量的个数

}

/*==================================================*\

| 弦图判断

| INIT: g[][]置为邻接矩阵;

| CALL: mcs(n); peo(n);

| 第一步: 给节点编号 mcs(n)

| 设已编号的节点集合为A, 未编号的节点集合为B

| 开始时A为空, B包含所有节点.

| for num=n-1 downto 0 do {

| 在B中找节点x, 使与x相邻的在A集合中的节点数最多,

| 将x编号为num, 并从B移入A.

| }

| 第二步: 检查 peo(n)

| for num=0 to n-1 do {

| 对编号为num的点x, 设所有编号>num且与x相邻的点集为C

| 在C中找出编号最小的节点y,

| 若C中存在点z!=y, 使得y与z之间无边, 则此图不是弦图.

| }

| 检查完了, 则此图是弦图.

\*==================================================*/

int g[V][V], order[V], inv[V], tag[V];

void mcs(int n){

int i, j, k;

memset(tag, 0, sizeof(tag));

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

for (i = n - 1; i >= 0; i--) { // vertex: 0 ~ n-1

for (j = 0; order[j] >= 0; j++) ;

for (k = j + 1; k < n; k++)

if (order[k] < 0 && tag[k] > tag[j]) j = k;

order[j] = i, inv[i] = j;

for (k = 0; k < n; k++) if (g[j][k]) tag[k]++;

}

int peo(int n){

int i, j, k, w, min;

for (i = n - 2; i >= 0; i--) {

j = inv[i], w = -1, min = n;

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

(g[j][k] && order[k] > order[j] &&

order[k] < min)

min = order[k], w=k;

if (w < 0) continue;

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

if (g[j][k] && order[k] > order[w] && !g[k][w])

return 0; // no

}

return 1; // yes

}

/*==================================================*\

| 弦图的 perfect elimination 点排列

| INIT: g[][]置为邻接矩阵;

| CALL: cardinality(n); tag[i]为排列中第i个点的标号;

| The graph with the property mentioned above

| is called chordal graph. A permutation s = [v1 , v2,

| ..., vn] of the vertices of such graph is called a

| perfect elimination order if each vi is a simplicial

| vertex of the subgraph of G induced by {vi ,..., vn}.

| A vertex is called simplicial if its adjacency set

| induces a complete subgraph, that is, a clique (not

| necessarily maximal). The perfect elimination order

| of a chordal graph can be computed as the following:

\*==================================================*/

procedure maximum cardinality search(G, s)

for all vertices v of G do

set label[v] to zero

end for

for all i from n downto 1 do

choose an unnumbered vertex v with largest label

set s(v) to i{number vertex v}

for all unnumbered vertices w adjacent to vertex v do

increment label[w] by one

end for

end procedure

int tag[V], g[V][V], deg[V], vis[V];

void cardinality(int n)

{

int i, j, k;

memset(deg, 0, sizeof(deg));

memset(vis, 0, sizeof(vis));

for (i = n - 1; i >= 0; i--) {

for (j = 0, k = -1; j < n; j++) if (0 == vis[j]) {

if (k == -1 || deg[j] > deg[k]) k = j;

}

vis[k] = 1, tag[i] = k;

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

if (0 == vis[j] && g[k][j]) deg[j]++;

}

/*==================================================*\

| 稳定婚姻问题 O(n^2)

\*==================================================*/

const int N = 1001;

struct People{

bool state;

int opp, tag;

int list[N]; // man使用

int priority[N]; // woman使用, 有必要的话可以和list合并，

以节省空间

void Init(){ state = tag = 0; }

}man[N], woman[N];

struct R{

int opp; int own;

}requst[N];

int n;

void Input(void);

void Output(void);

void stableMatching(void);

int main(void){

//...

Input();

stableMatching();

Output();

//...

return 0;

}

void Input(void){

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

int i, j, ch;

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

man[i].Init();

for( j=0; j < n; ++j ){ //按照man的意愿递减排序

scanf("%d", &ch); man[i].list[j] = ch-1;

}

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

woman[i].Init();

for( j=0; j < n; ++j ){ //按照woman的意愿递减排序，

但是，存储方法与man不同！！！！

scanf("%d", &ch); woman[i].priority[ch-1] = j;

}

void stableMatching(void){

int k;

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

int i, id = 0;

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

if( man[i].state == 0 ){

requst[id].opp =

man[i].list[ man[i].tag ];

requst[id].own = i;

man[i].tag += 1; ++id;

}

if( id == 0 ) break;

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

if( woman[requst[i].opp].state == 0 ){

woman[requst[i].opp].opp =

requst[i].own;

woman[requst[i].opp].state = 1;

man[requst[i].own].state = 1;

man[requst[i].own].opp =

requst[i].opp;

}

else{

if( woman[requst[i].opp].priority[ woman[requst[i].o

pp].opp ] >

woman[requst[i].opp].priority[requst[i].own] ){ //

man[ woman[requst[i].opp].opp ].state = 0;

woman[ requst[i].opp ].opp =

requst[i].own;

man[requst[i].own].state = 1;

man[requst[i].own].opp =

requst[i].opp;

}

void Output(void){

for( int i=0; i < n; ++i ) printf("%d\n", man[i].opp+1);

}

/*==================================================*\

| 拓扑排序

| INIT:edge[][]置为图的邻接矩阵;count[0…i…n-1]:顶点i的入度.

\*==================================================*/

void TopoOrder(int n){

int i, top = -1;

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

if( count[i] == 0 ){ // 下标模拟堆栈

count[i] = top; top = i;

}

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

if( top == -1 ) { printf("存在回路\n"); return ; }

else{

int j = top; top = count[top];

printf("%d", j);

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

if( edge[j][k] && (--count[k]) == 0 ){

count[k] = top; top = k;

}

/*==================================================*\

| 无向图连通分支(dfs/bfs 邻接阵)

| DFS / BFS / 并查集

\*==================================================*/

/*==================================================*\

| 有向图强连通分支(dfs/bfs 邻接阵)O(n^2)

\*==================================================*/

//返回分支数,id返回1..分支数的值

//传入图的大小n和邻接阵mat,不相邻点边权0

#define MAXN 100

void search(int n,int mat[][MAXN],int* dfn,int* low,int

now,int& cnt,int& tag,int* id,int* st,int& sp){

int i,j;

dfn[st[sp++]=now]=low[now]=++cnt;

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

if (mat[now][i]){

if (!dfn[i]){

search(n,mat,dfn,low,i,cnt,tag,id,st,sp);

if (low[i]<low[now])

low[now]=low[i];

}

else if (dfn[i]<dfn[now]){

for (j=0;j<sp&&st[j]!=i;j++);

if (j<cnt&&dfn[i]<low[now])

low[now]=dfn[i];

}

if (low[now]==dfn[now])

for (tag++;st[sp]!=now;id[st[--sp]]=tag);

}

int find_components(int n,int mat[][MAXN],int* id){

int ret=0,i,cnt,sp,st[MAXN],dfn[MAXN],low[MAXN];

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

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

if (!dfn[i])

search(n,mat,dfn,low,i,cnt,ret,id,st,sp);

return ret;

}

//有向图强连通分支,bfs邻接阵形式,O(n^2)

//返回分支数,id返回1..分支数的值

//传入图的大小n和邻接阵

mat,不相邻点边权0

#define MAXN 100

int find_components(int n,int mat[][MAXN],int* id){

int ret=0,a[MAXN],b[MAXN],c[MAXN],d[MAXN],i,j,k,t;

for (k=0;k<n;id[k++]=0);

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

if (!id[k]){

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

a[i]=b[i]=c[i]=d[i]=0;

a[k]=b[k]=1;

for (t=1;t;)

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

if (a[i]&&!c[i])

for (c[i]=t=1,j=0;j<n;j++)

if (mat[i][j]&&!a[j])

a[j]=1;

if (b[i]&&!d[i])

for (d[i]=t=1,j=0;j<n;j++)

if (mat[j][i]&&!b[j])

b[j]=1;

}

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

if (a[i]&b[i])

id[i]=ret;

}

return ret;

}

/*==================================================*\

剩余45页未读，继续阅读

oXiaoLiang1234

粉丝: 3
资源: 11

ACM算法代码库：从入门到精通

fluent14.5 UDF 官方手册

ACM 经典算法代码库(ACM 北大)

ACM算法代码库：图论与数论经典实现

ACM算法代码库：图论、网络流、数据结构等经典算法实现

ACM算法实现代码库（复习算法必备）

浙大ACM算法模板库

ACM算法代码集锦：图论与网络流

全面的ACM算法模板库

吉林大学ACM/ICPC算法代码库

吉林大学ACM团队算法代码库：图形理论与网络流

最新资源