ACM-ICPC算法模板：高效代码集，备战区域赛

需积分: 10 192 浏览量更新于2024-07-15 收藏 2.69MB PDF 举报

ACM-ICPC算法模板是一份由halfrost, 一个专注于计算机科学与工程领域的学生，专门为算法爱好者设计的文档。这份模板集合了作者自参加ACM国际大学生程序设计竞赛以来积累的高效代码，旨在为即将到来的区域赛做准备，目标是提高比赛成绩。模板中的代码经过作者精心调试和验证，确保了它们在时间效率上的优化。模板内容涵盖了图形理论和网络算法的核心部分，如非确定性搜索（NP搜索）下的最大团问题，以及对有向图和无向图连通性和强连通分量的多种算法。具体包括： 1. 最大团问题：这是一种经典图论问题，涉及寻找图中节点的最大子集，使得内部任意两个节点间都相连。 2. Kosaraju算法和 Tarjan算法：针对有向图的强连通分量，两种不同的求解方法，前者基于深度优先搜索，后者则是著名的 Tarjan算法，利用栈来找出强连通分量。 3. Gabow算法：另一种优化的算法，可能针对特定场景具有更好的性能。 4. 无向图连通分支：通过深度优先搜索（DFS）或广度优先搜索（BFS）实现的连通性检测，邻接矩阵是主要的数据结构。 5. 有向图强连通分支：同样使用DFS或BFS，但考虑到有向性，复杂度可能为O(n^2)。作者强调，虽然模板提供了基础的代码框架，但实际应用中需要灵活地根据题目要求进行调整和变通，这需要参赛者具备深入的理解和实践经验，这些技巧和经验是无法通过文档直接描述的，而是需要个人在实践中不断学习和积累。此外，模板中未包含动态规划（DP）内容，因为这部分内容作者已经研究过并记录在自己的笔记中，没有在此分享。同样，后缀数组、树状数组和并查集的高级技巧也未在文档中详述，鼓励读者自行探索和理解这些高级数据结构。最后，作者提到在完成文档时感受到了挑战，特别是了解到华中科技大学“精英班”的高难度，激发了他的决心。他计划通过不断练习，将更多代码转化为脑中的知识，减少对纸质资料的依赖，为未来的研究生考试和个人成长贡献力量。这份ACM-ICPC算法模板是一个实用的学习工具，它不仅提供基础代码，更是一种引导，鼓励读者通过实践和思考去掌握和提升算法技能。

Chapter 1

Graph Theory and Network Algorithms

1.1 NP

搜索

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

| 最大团问题（当 n<64 时，快速的模板见浙大模板）

| 最大独立集+最小覆盖集=V

| 最大团=补图的最大独立集

| 最小覆盖集=最大匹配

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

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int clique( int n,int *u,bool mat[][55],int size,int &max,int &bb,int *res,int

*rr,int *c){

int i,j,vn,v[55];

if (n){

if (size+c[u[0]]<=max) return 0;//要考虑的顶点数比已经有的最大

团数还要少，不再计算下去

for (i=0;i<n+size-max && i<n;i++){

for (j=i+1,vn=0;j<n;j++){

if (mat[u[i]][u[j]])

v[vn++]=u[j];

}

rr[size]=u[i];

clique(vn,v,mat,size+1,max,bb,res,rr,c);

if (bb) return 0;

}

else if (size>max){

max=size;

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

res[i]=rr[i];//res，用来存最大团的，也就是说 rr 存的是当前

的最大团顶点

}

bb=1;//根据这个算法的性质，在搜索下去 max 只会变小，所以

用 bb 标志，停止搜索

}

return 0;

}

int maxclique(int n,bool mat[][55],int *ret){

int max=0,bb,c[55],i,j;

int vn,v[55],rr[55];

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

for (vn=0,j=i+1;j<n;j++){

if (mat[i][j])v[vn++]=j;

}

bb=0;//可能是标志作用

rr[0]=i;

clique(vn,v,mat,1,max,bb,ret,rr,c);

c[i]=max;//这个记录的每次的最大个数

}

return max;

}

int main(){

// freopen ("1.txt","r",stdin);

int n,i,j;

bool mat[55][55];

int ret[55];

while (scanf("%d",&n)==1&&n){

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

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

scanf("%d",&mat[i][j]);

}

printf ("%d\n",maxclique(n,mat,ret));

}

return 0;

}

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

| 竞赛图

|图中任意两点,至少存在一条有向边，构成一个哈密顿(好像和哈密尔顿

|不同)路；

|对于一条以构建的哈密顿路的 n 个点(第 1 个点到第 n 个点,注意第 i 个

|点不一定是点 i ,eg,1 - 4 - 2 - 3,第 2 个点为 4，第 3 个点为 2，第 4

|个点为 3),插入第 n+1 个点，肯定找到一条有向路与之相连这里分 3

|种情况

|1> 第 n + 1 个点与第一个点相连，使第 n + 1 个点成为第一个点

|2> 最后一个点与第 n+1 个点相连，使第 n + 1 个点成为最后一个点

|3> 能在原哈密顿路中找到一个相连的点，第 i 个点和第 i+1 个点使

|得(第 i 个点与第 n+1 个点且第 n+1 个点与第 i+1 个点)相连，所以

|在第 i 个点与第 i+1 个点中插入第 n+1 个点

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

#include <iostream>

#define M 101

#include <list>

using namespace std;

bool f[ M ][ M ];

bool flag;

list <int> L;

list <int>::iterator it , pre;

void init (int n){

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

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

f[ i ][ j ] = false;

}

void solve (int n){

int i;

L.push_back(1);

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

it = L.begin ();

if (f[ i ][ *it ]){

L.push_front(i);

continue;

}

it = L.end();

-- it;

if (f[ *it ][ i ]){

L.push_back(i); continue;

}

it = pre = L.begin();

++ it;

while (it != L.end()){

if (f[ *pre ][ i ] && f[ i ][ *it ]){

L.insert(it , i);

break;

}

pre ++;

it ++;

}

int main(){

int t , n , i , k , g;

int a , b;

scanf ("%d" , &t);

while (t --){

L.clear();

scanf ("%d" , &n);

k = n * (n - 1) / 2;

init (n);

flag = true;

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

scanf ("%d %d" , &a , &b);

f[ a ][ b ] = true;

}

solve (n);

if (L.size() != n){

puts ("Impossible");

continue;

}

for (it = L.begin(); it != L.end();++ it){

if (it != L.begin()) printf (" ");

printf ("%d" , * it);

}

printf ("\n");

}

return 0;

}

1.2

连通性

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

| 有向图强连通分量 Kosaraju 算法

| 步骤

| 1.DFS 有向图 G，并以后根序记录节点

| 2.把存在于记录集中且最后访问节点作为起点，DFS 反图 GT,并以先根

| 序把节点从记录中剔除；

| 3.若此次不能 DFS 反图 GT 所有节点，则重复步骤 2，直到所有节点都

|被剔除出记录；每次剔除掉的节点集即为原有向图 G 的一个强连通分量

| 本算法慢，但是它得到了一个连通分量的拓扑序，有时用的上

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

#include <cstdio>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

#define NMAX 11000

vector< vector< int > > path;

vector< vector< int > > npath;

int n,m, scc;

int order[NMAX], order_pos, id[NMAX], id_total[NMAX];

bool vis[NMAX];

int out_degre[NMAX];

void dfs(int pos)

{

int i,j,l;

vis[pos] = true;

l = path[pos].size();

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

j = path[pos][i];

if (!vis[j]) {

dfs(j);

}

order[ order_pos ++ ] = pos;//make order

}

void ndfs(int pos)

{

int i,j,l;

vis[pos] = true;

id[pos] = scc;

l = npath[pos].size();

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

j = npath[pos][i];

if (!vis[j]) {

ndfs(j);

}

void Kosaraju()

{

int i,j,l;

//dfs in original graph

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

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

if (!vis[i]) {

dfs(i);

}

//dfs in inverse graph

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

memset(id, 0, sizeof(id));

scc = 1;

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

if (!vis[ order[i] ]) {

ndfs(order[i]);

scc ++;

}

//statist

scc --;

memset(id_total, 0, sizeof(id_total));

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

id_total[ id[i] ] ++;

}

memset(out_degre, 0, sizeof(out_degre));

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

l = path[i].size();

int id1 = id[i];

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

int id2 = id[ path[i][j] ];

if (id1 != id2) {//id1 -> id2

out_degre[id1] ++;

}

int ans_id,zero_degre = 0;

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

if (out_degre[i] == 0) {

zero_degre ++;

ans_id = i;

}

if (zero_degre > 1) {

printf("0\n");

}

else {

printf("%d\n",id_total[ ans_id ]);

}

int main()

{

int i,j;

while (scanf("%d %d",&n,&m)==2) {

path.resize(n+10);

npath.resize(n+10);

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

path[i].clear();

npath[i].clear();

}

order_pos = 0;

//set graph

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

int x,y;

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

path[x].push_back(y);

npath[y].push_back(x);

}

Kosaraju();

}

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

| 有向图强连通分量 Tarjan 算法

| 扩展：求出强连通后把强连通缩点是一个 DAG，对 DAG 求传递闭包

| 复杂度是 O(E)的，可借此求有向图的连通性。

| (poj 2553 The Bottom of a Graph )

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

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <set>

using namespace std;

const int MAXN = 5001;

int V, E;//点数、边数

int pt, ptR;

struct node

{

int v, next;//当前节点，下一节点位置

};

node adjlst[MAXN * 1000];//邻接表

bool sink[MAXN];

int prev[MAXN], low[MAXN], stk[MAXN], sc[MAXN];

int cnt[MAXN];

int cnt0, ptr, cnt1;

void dfs(int w)

{

int Min(0);

prev[w] = cnt0++;

low[w] = prev[w];

Min = low[w];

stk[ptr++] = w;

for(int i = adjlst[w].next; i != -1; i = adjlst[i].next)

{

int t = adjlst[i].v;

if(prev[t] == -1)

dfs(t);

if(low[t] < Min)

Min = low[t];

}

if(Min < low[w])

{

low[w] = Min;

return;

}

{

int v = stk[--ptr];

sc[v] = cnt1;

low[v] = MAXN;

}while(stk[ptr] != w);

++cnt1;

}

void Tarjan(int N)

{//传入 N 为点数，结果保存在 sc 数组中，同一标号的点在同一个强连通

分量内，

//强连通分量数为 cnt1

cnt0 = cnt1 = ptr = 0;

int i;

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

prev[i] = low[i] = -1;

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

if(prev[i] == -1)

dfs(i);

};

int last[MAXN];

int main()

{

int i, j;

for(; ;)

{

scanf("%d", &V);

if(!V) break;

scanf("%d", &E);

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

{

adjlst[i].next = -1;

last[i] = i;

}

pt = V;

ptR = V;

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

{

int a, b;

scanf("%d %d", &a, &b);

if(a == b) continue;

int pa = --a, pb = --b;

//while(adjlst[pa].next != -1)

pa = last[a]; //adjlst[pa].next;

adjlst[pa].next = pt;

adjlst[pt].v = b;

last[a] = pt;

adjlst[pt++].next = -1;

}

Tarjan(V);

set<int> kn;

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

{

for(int t = adjlst[i].next; t != -1; t = adjlst[t].next)

if(sc[i] != sc[adjlst[t].v])

{

kn.insert(sc[i]);

break;

}

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

sink[i] = false;

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

if(kn.find(sc[i]) == kn.end() ) sink[i] = true;

bool flag(false);

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

{

if(sink[i])

{

if(flag) printf(" ");

flag = true;

printf("%d", i + 1);

}

printf("\n");

}

return 0;

}

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

| 有向图强连通分量 Tarjan 算法(Tarjan 算法+静态邻接表)

| ////////只判断是否图上每两个点都连通，不输出路径

| (HDU 1269 迷宫城堡 )

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

#include <iostream>

#include <stack>

using namespace std;

typedef struct

{

long v,next;

}Edge;

typedef struct

{

long Num;

long Used;

long Alive;

long Low;

long belong;

void init(long pos)

{

Num=Used=Alive=Low=0;

belong=pos;

}

}Node;

const long MAXN=100010;

long N,M; //点，边

Edge e[MAXN]; //边数组

long p[MAXN/10]; //辅助数组

Node vec[MAXN/10]; //点

stack<long> s;

long Permit;//时间戳

inline void init()

{

long i;

while (!s.empty())

{

s.pop();

}

Permit=0;

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

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

{

vec[i].init(i);

}

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

{

long from,to;

scanf("%ld %ld",&from,&to);

e[i].next=p[from];

e[i].v=to;

p[from]=i;

}

inline void update(long &a,long b)

{

if(a>b) a=b;

}

inline void dfs(long pos)

{

s.push(pos);

vec[pos].Low=vec[pos].Num=++Permit;

vec[pos].Used=vec[pos].Alive=true;

long j;

for (j=p[pos];j!=-1;j=e[j].next){

long to=e[j].v;

if (vec[to].Used){

if (vec[to].Alive){

update(vec[pos].Low,vec[to].Num);

}

else

{

dfs(to);

update(vec[pos].Low,vec[to].Low);

}

if (vec[pos].Num==vec[pos].Low){

long t;

while ((t=s.top())!=pos){

vec[t].belong=pos;

vec[t].Alive=false;

s.pop();

}

vec[pos].belong=pos;

vec[pos].Alive=false;

s.pop();

}

inline void Tarjan(){

long i;

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

if (!vec[i].Used) {

dfs(i);

}

int main(){

while (scanf("%ld %ld",&N,&M)!=EOF){

if (N==0&&M==0){

break;

}

init();

Tarjan();

long i;

long t=vec[1].belong;

bool doit=true;

for (i=2;i<=N;++i){

if (vec[i].belong!=t){

doit=false;

break;

}

if (doit){

printf("Yes\n");

}

else{

printf("No\n");

}

return 0;

}

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

| 有向图强连通分量 Gabow 算法

| 速度比 Tarjan 快一点，但是一般还是用 Tarjan，

| 当 Tarjan 也会超时时候，只有这种方法了

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

#include<cstdio>

#include<cstring>

#define MAX 0x01010101

#define MIN(x,y) (x<y)?x:y

#define V 1005

#define E 5005

#define nStack 1005

struct node

{

int u, v;

node *nxt;

}*pp, pool[E], *adj[V];

int v, e;

int belong[V], nPart;

node * Add_Edge(int u, int v, node *Nxt)

{

pp->u = u;

pp->v = v;

pp->nxt = Nxt;

return pp++;

}

int stk1[nStack],top1;

int stk2[nStack],top2;

int low[V], num[V], times;

void DFS(int cur){

low[cur] = ++ times;

stk1[++ top1] = cur;

stk2[++ top2] = cur;

for (node * tp = adj[cur]; tp; tp = tp->nxt ){

int idx = tp->v;

if (low[idx] == MAX)//本点未曾访问

DFS(idx);

else if ( belong[idx] == 0 )//本点已经访问过，但是未有归属，即

在堆栈中

while ( low[stk2[top2]] > low[idx])

-- top2;

}

if ( stk2[top2] == cur )

{

-- top2; ++ nPart;

{

belong[stk1[top1]] = nPart;

}

while ( stk1[top1 --]!=cur );

}

void init(int Nv)

{

/*Pool*/

pp = pool;

memset(adj, 0, sizeof(adj[0]) * (Nv + 2));

/*DFS*/

memset(low, 0x01, sizeof(low[0]) *(Nv + 2) );

memset(belong, 0, sizeof(belong[0]) * (Nv + 2));

times = 0;

top1 = 0;

top2 = 0;

/*Main*/

nPart = 0;

}

//FUNCTION:

//Number of SCC

void QueryNp()

{

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

}

//Rebuild the Graph with SCC

bool ava[V][V];

void Rebuild(int Nv)

{

memset(ava, 0, sizeof(ava));

for (node *tp = pool; tp != pp; tp ++)

ava[belong[tp->u]][belong[tp->v]] = true;

for (int i = 1; i <= Nv; i ++) ava[i][i] = true;

}

void Floyd()

{

for (int k = 1; k <= nPart; k ++)

for (int i = 1; i <= nPart; i ++)

if (ava[i][k])

for (int j = 1; j <= nPart; j ++)

if (ava[k][j]) ava[i][j] = true;

}

int main()

{

while (scanf("%d%d", &v, &e) == 2 )

{

init(v);

while (e --)

{

int a, b;

scanf("%d%d", &a, &b);

adj[a] = Add_Edge(a, b, adj[a]);

}

for (int i = 1; i <= v; i ++)

if (low[i] == MAX) DFS(i);

Rebuild(v);

Floyd();

int Q;

scanf("%d", &Q); ////询问次数

while (Q --)

{

int a, b;

scanf("%d%d", &a, &b); ////询问哪两个点是否可连通

if (ava[belong[a]][belong[b]]) printf("Yes\n");

else printf("No\n");

}

return 0;

}

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

| 无向图连通分支(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;

}

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

| 有向图最小点基(邻接阵)O(n^2)

| 点基 B 满足：对于任意一个顶点 Vj，一定存在 B 中的一个 Vi,使得 Vi

是 Vj 的前代。

|返回点基大小和点基

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

|需要调用强连通分支

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

#define MAXN 100

int base_vertex(int n,int mat[][MAXN],int* sets){

int ret=0,id[MAXN],v[MAXN],i,j;

j=find_components(n,mat,id);

for (i=0;i<j;v[i++]=1);

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

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

if (id[i]!=id[j]&&mat[i][j])

v[id[j]-1]=0;

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

if (v[id[i]-1])

v[id[sets[ret++]=i]-1]=0;

return ret;

}

剩余145页未读，继续阅读

iOS逆向

粉丝: 5169
资源: 104

ACM-ICPC算法模板：高效代码集，备战区域赛

ACM-ICPC-Template:我的ICPC算法代码模板

ACM/ICPC算法大全(c语言)

ACM的常用算法模板.pdf

ACM/ICPC 代码库

Data-Structure-and-Algorithm:竞争性编程

Algorithm_with_Cpp

ACM_HDU:在 hdoj 中解决了我的 acm 问题的一部分

algorithm_practice

ACMCode:ACM 代码集

ACM竞赛与STL

最新资源