ACM经典算法总结+代码实现~-白红宇

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

阅读量：2439 次

发布时间：2019-05-10

本文共 9520 字，大约阅读时间需要 31 分钟。

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

/********************************************** *Author*        :coderdz *Created Time*  : 2019/1/7 23:31:48*********************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                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
                
                  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

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]=0n=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)

2.汉诺塔（个人觉得最难理解的递归问题之一）

求出对于不同的n(盘块个数)的移动方法

#include
   
    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=0solve_hanno(n,'A','B','C')

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

/********************************************** *Author*        :coderdz *Created Time*  : 2019/1/17 21:51:00*********************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                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
                
                  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

4.迷宫问题（bfs遍历）

输入一个字符迷宫矩阵，'.'代表可以通过，'#'代表不能通过，S为起点，G为终点，计算起点到终点的最短距离

/********************************************** *Author*        :coderdz *Created Time*  : 2019/1/7 23:31:48*********************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                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
                
                  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
                 
                   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
                  
                   =0&&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

5.最短路之floyed算法

O(n^3),多源最短路径

/********************************************** *Author*        :coderdz *Created Time*  : 2019/1/7 23:31:48*********************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                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
                
                  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;}

6.最短路之Dijkstra算法

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

/********************************************** *Author*        :coderdz *Created Time*  : 2019/1/7 23:31:48*********************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                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
                
                  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]

7.最短路之SPFA算法

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

/********************************************** *Author*        :coderdz *Created Time*  : 2019/1/18 16:39:22*********************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                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
                
                  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
                 
                   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]

8.最小生成树（Kruskal算法）

适用于稀疏图

/********************************************** *Author*        :coderdz *Created Time*  : 2019/1/19 15:07:16*********************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                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
                
                  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

9.并查集

/********************************************** *Author*        :coderdz *Created Time*  : 2019/1/19 14:19:26*********************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                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
                
                  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;}

10.树状数组（BIT）

能够完成下述操作的数据结构j（优点是速度快）：

给定初始值全为0的数列a1,a2,a3,·····,an

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

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

/********************************************** *Author*        :coderdz *Created Time*  : 2019/1/19 21:40:52树状数组*********************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                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
                
                  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;}