ACMクラシックアルゴリズムまとめ+コード実装~

13354 ワード
acmの道 アルゴリズム#アルゴリズム#
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]=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)

2.ハノータ(個人的に最も理解しにくい再帰問題の一つ)
異なるn(ディスクブロック個数)に対する移動方法を求める
#include

int cnt=0;

void move(int id,char a,char c){//      ：        ？
	printf("step %d :move %d from %c ---> %c
",++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')

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
",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("
");
    return 0;
}

10.ツリー配列(BIT)
以下のような動作を行うことができるデータ構造j(高速の利点):
与えられた初期値がすべて0の数列a 1,a 2,a 3,・・,an
1)iが与えられ、a 1+a 2+・・+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("
");
	rep(i,n) printf("%3d ",bit[i]);//    
	printf("
");
	rep(i,n) printf("%3d ",sum(i));//   
	printf("
");
	return 0;
}

ソートアルゴリズム——バブルソート【コード実装】
【社内勉強会】Git初心者から卒業するための準備(2017/03/28)