搜索
您的当前位置：首页正文

各种内容转载以及PS

来源：步旅网

 

 

快速幂,矩阵快速幂原理介绍

背包问题总结

最大流学习内容

（最大流）

EK算法：BFS来寻找增广路       Dinic：(用到层次图)              FF算法：DFS来寻找增广路

（三种算法）

（EK和FF的不同，FF比较慢）

（最大流就是最小割）

EK算法：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<queue>
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define rep1(i,s,e) for(int i=s;i<e;i++)
#define rep2(i,s,e,c) for(int i=s;i>=e;i--)
#define pfi(x) printf("%d\n",x)
#define pfl(x) printf("%lld\n",x)
#define pfn() printf("\n")
#define pfs() printf(" ")
#define sfi(x) scanf("%d",&x)
#define sfi1(x,y) scanf("%d%d",&x,&y)
#define sff(x) scanf("%lf",&x)
#define sfl(x) scanf("%lld",&x)
#define memset1(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;
const int MAX = 1e4 + 50;
const int mod = 996873654;
int capacity[MAX][MAX];//容量 
int flow[MAX],pre[MAX];//每个点的流量和前节点 
int n,m;//边数n以及汇点m,源点是1
int BFS(int src,int des){//BFS寻找增广路 
	queue<int> q;
	memset(pre,-1,sizeof(pre));
	pre[src]=0;
	flow[src]=0x3f3f3f3f;//将源点的流量设为无限
	q.push(src);
	while(!q.empty()){
		int index = q.front();
		q.pop();
		if(index == des) break; //找到了增广路
		rep1(i,1,m){
			if(capacity[index][i]>0 && pre[i]==-1){
				pre[i]=index;
				flow[i]=min(capacity[index][i],flow[index]);
				q.push(i);
			}
		} 
	}
	//如果找到增广路返回该条增广路最大流量，否则返回-1 
	if(pre[des]!=-1){
		return flow[des];
	}
	else return -1;
}
int maxFlow(int src,int des){//最大流函数 
	int increasement=0;
	int sumflow=0;
	while((increasement==BFS(src,des))!=-1){
		int k = des;
		while(k!=src){
			int last = pre[k];
			capacity[last][k]-=increasement;//改变正向边的容量
			capacity[k][last]+=increasement;//改变反向边的容量
			k = last; 
		}
		sumflow+=increasement;
	}
	return sumflow;
}
int main(){
	while(cin>>n>>m){
		memset1(capacity);
		memset1(flow);
		rep(i,1,n){
			int start,end,ci;
			cin>>start>>end>>ci;
			if(start == end) continue; //两点相同的情况，不过一般出题不会有这种情况吧 
			capacity[start][end]+=ci;//注意出现重复的情况 
		}
		cout<<maxFlow(1,m)<<endl;
	}
	return 0;
}

FF算法

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<queue>
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define rep1(i,s,e) for(int i=s;i<e;i++)
#define rep2(i,s,e,c) for(int i=s;i>=e;i--)
#define pfi(x) printf("%d\n",x)
#define pfl(x) printf("%lld\n",x)
#define pfn() printf("\n")
#define pfs() printf(" ")
#define sfi(x) scanf("%d",&x)
#define sfi1(x,y) scanf("%d%d",&x,&y)
#define sff(x) scanf("%lf",&x)
#define sfl(x) scanf("%lld",&x)
#define memset1(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;
const int MAX = 1e4 + 50;
const int mod = 996873654;
int n,m;
int used[MAX];
int capacity[MAX][MAX];
int DFS(int src,int des,int max_capacity){
	if(src==des) return max_capacity;//只要找到增广路，直接返回 
	rep(i,1,n){
		if(capacity[src][i]>0 && !used[i]){
			used[i]=1;//因为只用找到一条增广路就可以，所以不用重置为0 
			int d=DFS(i,des,min(max_capacity,capacity[src][i]));
			if(d>0){
				capacity[src][i]-=d;
				capacity[i][src]+=d;
				return d;
			}
		}
	}
	return -1;
}
int maxFlow(int src,int des){
	int flow=0;
	int increasement;
	memset1(used);
	used[1]=1;
	while((increasement=DFS(src,des,0x3f3f3f3f))!=-1){
		flow+=increasement;
		memset1(used);
		used[1]=1;
	}
	return flow;
}
int main(){
	int des;
	while(cin>>n>>m>>des){
		memset1(capacity);
		rep(i,1,m){
			int start,end,ci;
			cin>>start>>end>>ci;
			capacity[start][end]+=ci;//注意出现重复的情况 
		}
		cout<<maxFlow(1,des)<<endl;
	}
	return 0;
}
/*
4 5 3
1 2 40
1 4 20
2 3 30
2 4 20
3 4 10
*/

 Dinic算法

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<queue>
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define rep1(i,s,e) for(int i=s;i<e;i++)
#define rep2(i,s,e,c) for(int i=s;i>=e;i--)
#define pfi(x) printf("%d\n",x)
#define pfl(x) printf("%lld\n",x)
#define pfn() printf("\n")
#define pfs() printf(" ")
#define sfi(x) scanf("%d",&x)
#define sfi1(x,y) scanf("%d%d",&x,&y)
#define sff(x) scanf("%lf",&x)
#define sfl(x) scanf("%lld",&x)
#define memset1(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;
const int MAX = 1e4 + 50;
const int mod = 996873654;
int n,m,des;
int capacity[MAX][MAX];
int dep[MAX];//各点层次
bool build_dep(int src,int des){//BFS构建层次图 
	queue<int> q;
	memset1(dep);
	dep[src]=1;
	q.push(src);
	while(!q.empty()){
		int index = q.front();
		q.pop();
		rep(i,1,n){
			if(capacity[index][i]>0 && !dep[i]){
				dep[i]=dep[index]+1;
				q.push(i);
			}
		}
	}
	return dep[des]?true:false;
}
int DFS(int src,int des,int max_capacity){//DFS寻找增广路 
	if(src==des) return max_capacity;
	rep(i,1,n){
		if(capacity[src][i]>0 && dep[src]+1==dep[i]){
			int d = DFS(i,des,min(capacity[src][i],max_capacity));
			if(d>0){
				capacity[src][i]-=d;
				capacity[i][src]+=d;
				return d;
			}
		}
	}
	return -1;
}
int maxFlow(int src,int des){
	int flow=0,increasement;
	if(!build_dep(src,des)) return 0;
	while((increasement=DFS(src,des,0x3f3f3f3f))!=-1){
		flow+=increasement;
	}
	return flow;
}
int main(){
	int des;
	while(cin>>n>>m>>des){
		memset1(capacity);
		rep(i,1,m){
			int start,end,ci;
			cin>>start>>end>>ci;
			capacity[start][end]+=ci;//注意出现重复的情况 
		}
		cout<<maxFlow(1,des)<<endl;
	}
	return 0;
}
/*
4 5 3
1 2 40
1 4 20
2 3 30
2 4 20
3 4 10
*/

ACM：悬线法

康托展开&逆康托展开

康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。设有n个数（1，2，3，4,…,n），可以有组成不同(n!种)的排列组合，康托展开表示的就是是当前排列组合在n个不同元素的全排列中的名次。

数码问题

n*n的网格，如果n为奇数，当奇数码游戏两个局面可达，当且仅当两个局面下网格中的数依次写成1行n*n-1个元素的序列后（不考虑空格），逆序对个数的奇偶性相同。

证明：空格左右移动时，写成的序列显然不变；空格上（下）移动时，相当于某个数与它后（前）边的n-1个数交换了位置，因为n-1是偶数，所以逆序对的变化也只能是偶数。

如果n为偶数，两个局面可达，当且仅当两个局面对应网格写成序列后，“逆序对数之差”和“两个局面下空格所在的行数只差”奇偶性相同。事实上，n*m网格上(n,m>=2)也服从上述两个结论之一（根据列数奇偶性分情况讨论）

总而言之，n*m数码问题的有解性判定，可以转化为归并排序求逆序对来解决。

多项式

三次以上的多项式一定可以因式分解

A*算法

自己写的，也没怎么测试，错了勿怪

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define rep1(i,s,e) for(int i=s;i<e;i++)
#define rep2(i,s,e,c) for(int i=s;i>=e;i--)
#define pfi(x) printf("%d\n",x)
#define pfl(x) printf("%lld\n",x)
#define pfn() printf("\n")
#define pfs() printf(" ")
#define sfi(x) scanf("%d",&x)
#define sfi1(x,y) scanf("%d%d",&x,&y)
#define sff(x) scanf("%lf",&x)
#define sfl(x) scanf("%lld",&x)
#define memset1(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;
const int MAX = 8e3+50;
const int mod = 996873654;
int n,m;//n行m列 
//假设可以走八个方向，而且直走cost为10，斜走cost为14(简单)
int xy[][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};
struct vis{
	int walkable;
	bool close_list;
	bool open_list;
	//int cost;//题目中可能会出现的代价，比如在沼泽中花费更多的体力
	int fromX,fromY;
	int f,g,h;//f=g+h,用曼哈顿距离估算h,g为移动代价
}mmap[MAX][MAX];
struct node{
	int x,y;
	node(): x(0), y(0){}
	void init(int _x,int _y){
		x=_x; y=_y;
	}
	void calculate(node des){
		mmap[x][y].g=mmap[mmap[x][y].fromX][mmap[x][y].fromY].g;
		if(x==mmap[x][y].fromX || y==mmap[x][y].fromY) mmap[x][y].g+=10;
		else mmap[x][y].g+=14;
		mmap[x][y].h=abs(x-des.x)+abs(y-des.y);
		mmap[x][y].f=mmap[x][y].g+mmap[x][y].h;
	}
	bool judge(node p,node des){
		if(!mmap[x][y].walkable || mmap[x][y].close_list) return false;
		if(x>=1&&x<=n&&y>=1&&y<=m){
			if(!mmap[x][y].open_list){
				mmap[x][y].open_list=true;
				mmap[x][y].fromX=p.x; mmap[x][y].fromY=p.y;
				calculate(des);
				return true;
			}
			else{
				int newg=mmap[p.x][p.y].g;
				if(p.x==x || p.y==y) newg+=10;
				else newg+=14;
				if(newg<mmap[x][y].g){
					mmap[x][y].fromX=p.x; mmap[x][y].fromY=p.y;
					mmap[x][y].g=newg;
					mmap[x][y].f=mmap[x][y].g+mmap[x][y].h;
					return true;
				}
				else return false;
			}
		}
	}
	bool operator == (const node& temp) const{
		if(x==temp.x && y==temp.y) return true;
		else return false;
	}
	bool operator < (const node& temp) const{
		return mmap[x][y].f>mmap[temp.x][temp.y].f;
	}
}src,des,p,p1;
priority_queue<node> q;
void Astar(){
	while(!q.empty()) q.pop();
	q.push(src);
	mmap[src.x][src.y].open_list=true;
	while(!q.empty()){
		p = q.top();
		q.pop();
		mmap[p.x][p.y].close_list=true;
		mmap[p.x][p.y].open_list=false;
		if(p==des) break;
		rep1(i,0,8){
			p1.init(p.x+xy[i][0],p.y+xy[i][1]);
			if(p1.judge(p,des)){
				q.push(p1);
			}
		}	
	}
}
int main(){
	while(cin>>n>>m){
		rep(i,1,n){
			rep(j,1,m){
				sfi(mmap[i][j].walkable);
			}
		}
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		src.init(x1,y1); des.init(x2,y2);
		Astar();
		if(mmap[des.x][des.y].walkable && mmap[des.x][des.y].close_list){
			stack<node> st;
			p.init(des.x,des.y);
			while(1){
				st.push(p);
				if(p==src) break;
				p.init(mmap[p.x][p.y].fromX,mmap[p.x][p.y].fromY);
			} 	
			while(st.size()){
				p=st.top();
				st.pop();
				cout<<p.x<<" "<<p.y<<"\n";
			}
		}
	}
	return 0;
}
/*
5 7
1 1 1 1 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 1 1 1 1
3 2 3 6
*/

IDA*算法

算法题目：

A*算法概述：
     采用广度优先搜索策略，在搜索过程中使用启发函数，即有大致方向的向前进虽然目标有时候不是很明确。
A*算法核心：
     A*算法的关键在于启发函数，启发函数的优劣直接影响A*算法的效率。
          f(n)=g(n)+h(n); 
     这个式子中：f(n)表示从初始状态到目标状态的估测代价。
                         g(n)表示从初始状态到当前状态的代价（已经确定）。
                         h(n)表示从当前状态到目标状态的估测代价(预测）。
                 其中：h(n)的好坏直接影响评估函数的好坏。
                 一个好的f(n)总能明确指引算法前进的方向，可以迅速的到达目标状态。
            f*(n)=g*(n)+h*(n); 我们假设的从初始状态到目标状态的实际最小代价。
      这个式子中：f(n)表示从初始状态到目标状态的实际代价。
                         g*(n)表示从初始状态到当前状态的代价（已经确定）g*(n)和g(n)是相等的。
                         h*(n)表示从当前状态到目标状态的实际代价。
                若h(n)<=h*(n),则总能找到最优解。（当h(n)<h*(n)的时候，不可能找到一条从初始状态到达目标状态的路径。在搜索过程中使得h(n)逐渐接近h*(n)，最终找到最优路径。
          
优点：
      与广度优先搜索策略和深度优先搜索策略相比，A*算法不是盲目搜索，而是有提示的搜索。
缺点：
     该算法一般要使用大量的空间用于存储已搜索过的中间状态，防止重复搜索。
用途：
     从初始状态出发  =>经过一系列中间状态 =>最终到达目标状态（或者无法到达）。
     该算法用于经过中间状态时候的行进策略（其中的中间状态或者由题目给出，或者在前边已经推导得出）。


IDA*算法：
     迭代加深搜索算法，在搜索过程中采用估值函数，以减少不必要的搜索。
IDA*算法核心：
     设置每次可达的最大深度depth，若没有到达目标状态则加深最大深度。
     采用估值函数，剪掉f(n)大于depth的路径。
优点：
     使用回溯方法，不用保存中间状态，大大节省了空间。
缺点：
     重复搜索：回溯过程中每次depth变大都要再次从头搜索。
用途：
     和A*算法大致相同。
     


实际上，估测函数f(n)也是剪枝的一种。

DFS序

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

Copyright © 2019- 版权所有

Top