ACM经典代码总结+代码实现~

数的全排列（最基础的dfs回溯）

 
/**********************************************
 *Author*        :coderdz
 *Created Time*  : 2019/1/7 23:31:48
*********************************************/
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
#define IO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,n) for(int i=1;i<=n;i++)
#define m(a,b) memset(a,b,sizeof(a))
typedef pair<int, int> PII;
typedef long long LL;
const int MAXN=1e5+10;
 
inline void OPEN(string s){
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
 
int n,a[100],vis[100];
 
void dfs(int x){
	if (x>n){
		for(int i=1;i<n;i++)
			printf("%d ",a[i]);
		printf("%d\n",a[n]);
	}
	else{
		for(int i=1;i<=n;i++){
			if (!vis[i]){
				vis[i]=1;
				a[x]=i;
				dfs(x+1);
				vis[i]=0;
			}
		}
	}
}
 
int main(){
    scanf("%d",&n);
    m(vis,0);
    dfs(1);
    return 0;
}

python版:

def dfs(x):
	if x>n:
		for i in range (1,n):
			print(a[i],end=' ')
		print(a[n])
	else:
		for i in range(1, n+1):
			if vis[i]==0:
				vis[i]=1
				a[x]=i
				dfs(x+1)
				vis[i]=0
 
n=int(input())
vis=[0]
a=[0]
for i in range(1,n+1):
	vis.append(0)
for i in range(1,n+1):
	a.append(0)
dfs(1)

汉诺塔（个人觉得最难理解的递归问题之一）
求出对于不同的n(盘块个数)的移动方法

#include<cstdio>
 
int cnt=0;
 
void move(int id,char a,char c){//打印移动方式：哪个盘子怎么移动？
	printf("step %d :move %d from %c ---> %c\n",++cnt,id,a,c);
}
 
void solve_hanno(int n,char a,char b,char c){//递归过程
	if (n==1) move(n,a,c);
	else{
		solve_hanno(n-1,a,c,b);
		move(n,a,c);
		solve_hanno(n-1,b,a,c);
	}
}
 
int main(){
	int n;
	scanf("%d",&n);
	solve_hanno(n,'A','B','C');
	return 0;
}

python版:

def move(n,a,c):
	global cnt #定义cnt全局变量，可进行读写
	cnt+=1
	print('step %d: move %d from %c ---> %c' % (cnt,n,a,c))
	
def solve_hanno(n,a,b,c):
	if n==1:
		move(n,a,c)
	else:
		solve_hanno(n-1,a,c,b)
		move(n,a,c)
		solve_hanno(n-1,b,a,c)
 
n=int(input())
cnt=0
solve_hanno(n,'A','B','C')

八皇后问题（经典dfs回溯）

/**********************************************
 *Author*        :coderdz
 *Created Time*  : 2019/1/17 21:51:00
*********************************************/
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
#define IO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,n) for(int i=1;i<=n;i++)
#define m(a,b) memset(a,b,sizeof(a))
typedef pair<int, int> PII;
typedef long long LL;
const int MAXN=1e5+10;
int ans=0,a[15],b[15];
 
bool check(int row){
	for(int i=1;i<row;i++){
		if (a[i]==a[row] || abs(row-i)==abs(a[row]-a[i]))
			return false;
	}
	return true;
}
 
void dfs(int row,int n){//每个皇后放一行,只需要确定放哪一列
	if (row==n+1) ans++;//n行全部放完了,答案+1
	else{
		for(int i=1;i<=n;i++){//枚举1~n列尝试
			a[row]=i;//皇后放置在row行,i列
			if (check(row))
				dfs(row+1,n);
		}
	}
}
 
int main(){
	int n;
    scanf("%d",&n);
    dfs(1,n);
    printf("%d\n",ans);
    return 0;
}

迷宫问题（bfs遍历）
输入一个字符迷宫矩阵，’.’代表可通过，’#’代表不能通过，’S’为起点，’G’为终点
求出起点到终点的所有路径中最短的一条

/**********************************************
 *Author*        :coderdz
 *Created Time*  : 2019/1/7 23:31:48
*********************************************/
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
#define IO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,n) for(int i=1;i<=n;i++)
#define m(a,b) memset(a,b,sizeof(a))
typedef pair<int, int> PII;
typedef long long LL;
const int MAXN=1e5+10;
int n,m,dis[105][105]={0};
int sx,sy,gx,gy;//起点和终点坐标
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};//四个方向移动
char s[105][105];
 
void bfs(){
	queue<PII> q;
	q.push(PII(sx,sy));
	dis[sx][sy]=0;
	while(q.size()){//队列不为空
		PII p=q.front();
		q.pop();
		if (p.first==gx && p.second==gy) break;
		for(int i=0;i<4;i++){
			int x=p.first+dx[i];
			int y=p.second+dy[i];
			if (x<n&&x>=0&&y<m&&y>=0&&s[x][y]!='#'&&dis[x][y]==0){
				dis[x][y]=dis[p.first][p.second]+1;
				q.push(PII(x,y));
			}
		}	
	}
}
 
void init(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf(" %c",&s[i][j]);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++){
			if (s[i][j]=='S'){
				sx=i;
				sy=j;
			}
			else if (s[i][j]=='G'){
				gx=i;
				gy=j;
			}
		}
}
 
int main(){
	init();
	bfs();
	printf("%d\n",dis[gx][gy]);
	return 0;
}

最短路之Floyed算法
O(n^3),多源最短路径

/**********************************************
 *Author*        :coderdz
 *Created Time*  : 2019/1/7 23:31:48
*********************************************/
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
#define IO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,n) for(int i=1;i<=n;i++)
#define m(a,b) memset(a,b,sizeof(a))
typedef pair<int, int> PII;
typedef long long LL;
const int MAXN=105;
int n,m,f[MAXN][MAXN];
 
int main(){
	scanf("%d%d",&n,&m);//无向图,n个点,m条边
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if (i==j) f[i][j]=0;
			else f[i][j]=1<<30;
		}
	int u,v,w;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		f[u][v]=min(f[u][v],w);
	}
	for(int k=1;k<=n;k++)//枚举中间点,必须放外层
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if (f[i][j]>f[i][k]+f[k][j])
					f[i][j]=f[i][k]+f[k][j];
	printf("%d\n",f[1][n]);//节点1到节点n的距离
	return 0;
}

最短路之Dijkstra算法
O(n^2),单源最短路径,不能处理负边权

/**********************************************
 *Author*        :coderdz
 *Created Time*  : 2019/1/7 23:31:48
*********************************************/
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
#define IO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,n) for(int i=1;i<=n;i++)
#define m(a,b) memset(a,b,sizeof(a))
typedef pair<int, int> PII;
typedef long long LL;
const int MAXN=1e5;
int n,m,all;
int pre[MAXN],last[MAXN],other[MAXN],cost[MAXN],dis[MAXN],vis[MAXN];
 
void build(int u,int v,int w){
	pre[++all]=last[u];
	last[u]=all;
	other[all]=v;
	cost[all]=w;
}
 
void dijkstra(){
	for(int i=1;i<=n;i++){
		if (i==1) dis[i]=0;
		else dis[i]=1<<30;
	}
	int now=1;
	for(int i=1;i<=n;i++){
		vis[now]=1;//选入的点标记为1
		int ed=last[now];
		while(ed!=-1){//遍历当前点相连的所有边然后进行松弛
			int dr=other[ed];
			if (!vis[dr])
				dis[dr]=min(dis[dr],dis[now]+cost[ed]);//松弛
			ed=pre[ed];
		}
		int pos,Min=1<<30;
		for(int i=1;i<=n;i++)//找到松弛后与当前点距离最短的点
			if (!vis[i])
				if (dis[i]<Min)
					Min=dis[i],pos=i;
		now=pos;
	}
}
 
int main(){
	scanf("%d%d",&n,&m);
	m(last,-1);
	m(vis,0);
	all=-1;
	for(int i=1;i<=m;i++){
		int a,b,w;
		scanf("%d%d%d",&a,&b,&w);
		build(a,b,w);
		build(b,a,w);
	}
	dijkstra();
	printf("%d\n",dis[n]);
	return 0;
}

最短路之SPFA算法
队列优化的Bellman-Ford算法,单源最短路,负权值但无环状图,O(KE)

/**********************************************
 *Author*        :coderdz
 *Created Time*  : 2019/1/18 16:39:22
*********************************************/
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
#define IO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,n) for(int i=1;i<=n;i++)
#define m(a,b) memset(a,b,sizeof(a))
typedef pair<int, int> PII;
typedef long long LL;
const int MAXN=1e5+10;
int n,m,all;
int pre[MAXN],last[MAXN],other[MAXN],cost[MAXN],dis[MAXN];
bool vis[MAXN];
 
void build(int u,int v,int w){
	pre[++all]=last[u];
	last[u]=all;
	other[all]=v;
	cost[all]=w;
}
 
void bfs(int s){
	int now,ed,dr;
	queue<int> q;
	q.push(s);
	for(int i=1;i<=n;i++){
		if (i==s) dis[i]=0;
		else dis[i]=1<<30;
	}
	vis[s]=1;
	while(q.size()){
		now=q.front();
		q.pop();
		ed=last[now];
		while(ed!=-1){
			dr=other[ed];
			if (dis[now]+cost[ed]<dis[dr]){
				dis[dr]=dis[now]+cost[ed];
				if (!vis[dr]){
					vis[dr]=1;
					q.push(dr);
				}
			}
			ed=pre[ed];
		}
		vis[now]=0;
	}
}
 
int main(){
	all=-1;
	m(last,-1);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int a,b,w;
		scanf("%d%d%d",&a,&b,&w);
		build(a,b,w);
		build(b,a,w);
	}
    m(vis,0);
    bfs(1);
    printf("%d\n",dis[n]);
    return 0;
}

最小生成树（Kruskal算法）
适用于稀疏图

/**********************************************
 *Author*        :coderdz
 *Created Time*  : 2019/1/19 15:07:16
*********************************************/
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
#define IO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,n) for(int i=1;i<=n;i++)
#define m(a,b) memset(a,b,sizeof(a))
typedef pair<int, int> PII;
typedef long long LL;
const int MAXN=1e5+10;
int fa[MAXN],n,m;
 
struct Node{
	int u,v,w;
}node[MAXN];
 
bool cmp(Node a,Node b){
	return a.w<b.w;
}
 
int find(int x){
	if (x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
 
void kruscal(){
	int sum=0;
	rep(i,m){
		int u=node[i].u,v=node[i].v;
		if (find(u)!=find(v)){//合并这两个点到一棵树上
			fa[find(v)]=find(u); 
			sum+=node[i].w;
		}//若两个点在同一棵树上,则舍弃掉这条边,不加到sum中
	}
	printf("%d\n",sum);
}
 
void init(){
	while(~scanf("%d%d",&n,&m)){
		if (!n) break;
		rep(i,n) fa[i]=i;
		rep(i,m) scanf("%d%d%d",&node[i].u,&node[i].v,&node[i].w);
		sort(node+1,node+1+m,cmp);//对图的边进行从小到大排序,每次取最小的边
		kruscal();
	}
}
 
int main(){
    //IO;
    init();
    return 0;
}

并查集

/**********************************************
 *Author*        :coderdz
 *Created Time*  : 2019/1/19 14:19:26
*********************************************/
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
#define IO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,n) for(int i=1;i<=n;i++)
#define m(a,b) memset(a,b,sizeof(a))
typedef pair<int, int> PII;
typedef long long LL;
const int MAXN=1e5+10;
 
int fa[MAXN],n,m;
 
 
int find(int x){//查找根节点
	if (fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
 
void join(int x,int y){//合并(y合并到x上)
	int fx=find(x),fy=find(y);
	if (fx!=fy) fa[fy]=fx;
}
 
void init(){//初始化
	scanf("%d%d",&n,&m);
	rep(i,n) fa[i]=i;
	rep(i,m){
		int a,b;
		scanf("%d%d",&a,&b);
		join(a,b);
	}
}
 
int main(){
	//IO;
	init();
	for(int i=1;i<=n;i++)
		printf("%d ",find(i));
	printf("\n");
    return 0;
}

树状数组（BIT）
能够完成下述操作的数据结构(优点是速度快)：
给定初始值全为0的数列a1,a2,a3,·····,an

给定i，计算a1+a2+···+ai

给定ai和x，执行ai+=x

/**********************************************
 *Author*        :coderdz
 *Created Time*  : 2019/1/19 21:40:52
树状数组
*********************************************/
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
#define IO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,n) for(int i=1;i<=n;i++)
#define m(a,b) memset(a,b,sizeof(a))
typedef pair<int, int> PII;
typedef long long LL;
const int MAXN=5e4+10;
int bit[MAXN],n,a[MAXN];
 
int lowbit(int x){//求某个数二进制表示中最低的一位1
	return x&(-x);
}
 
void add(int i,int x){
	while(i<=n){
		bit[i]+=x;
		i+=lowbit(i);
	}
}
 
int sum(int i){//求1~i的前缀和
	int ans=0;
	while(i>0){
		ans+=bit[i];
		i-=lowbit(i);
	}
	return ans;
}
 
int main(){
	m(bit,0);
	n=20;
	rep(i,n) a[i]=i;
	rep(i,n) add(i,a[i]);
	rep(i,n) printf("%3d ",a[i]);//原数组
	printf("\n");
	rep(i,n) printf("%3d ",bit[i]);//前缀数组
	printf("\n");
	rep(i,n) printf("%3d ",sum(i));//前缀和
	printf("\n");
	return 0;
}