标签：printf   ems   lowbit   next   +=   c++   priority   初始   jks   

最短路

SPFA

#include 
using namespace std;
#define N 10001
#define M 500001 
struct node{
	int to,w,next;
}edge[M];
int cut=0;
int head[N];
int dis[N];
int n,m,k;
bool vis[N];
queue q;
void ini(){
	fill(dis+1,dis+N+1,INT_MAX);
	memset(head,-1,sizeof(head));
}
void add(int u,int v,int w){//建边 
	cut++;
	edge[cut].w=w;
	edge[cut].to=v;
	edge[cut].next=head[u];
	head[u]=cut;
}
void SPFA(int x){
	dis[x]=0;
	q.push(x);//头入队 
	vis[x]=1;
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=false;
		for(int j=head[u];~j;j=edge[j].next){//调用邻接表 
			if(dis[edge[j].to]>dis[u]+edge[j].w){
				dis[edge[j].to]=dis[u]+edge[j].w;//松弛操作 
				if(!vis[edge[j].to]){//判断标记 
					q.push(edge[j].to);//入队边上的点 
					vis[edge[j].to]=1;//标记 
				}
			}
		}
	}
} 
int main(){
	
	ini();
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1,u,v,w;i

Dijkstra（堆优化）

#include 
using namespace std;
#define N 10001
#define M 500001 
#define P pair  
#define Fi first
#define Se second
struct node{
	int to,w,next;
}edge[M];
int cut=0;
int head[N];
int dis[N];
int n,m,k;
bool vis[N];
priority_queue
,greater
 > q;//优先队列 
void ini(){
	fill(dis+1,dis+N+1,INT_MAX);
	memset(head,-1,sizeof(head));
}
void add(int u,int v,int w){
	cut++;
	edge[cut].w=w;
	edge[cut].to=v;
	edge[cut].next=head[u];
	head[u]=cut;
}
void Dij(int x){
	dis[x]=0;
	vis[x]=1;
	q.push(P(0,x));//头入队 
	while(!q.empty()){
		P u=q.top();q.pop();vis[u.Se]=1;
		for(int j=head[u.Se];~j;j=edge[j].next){//邻接表遍历 
			if(!vis[edge[j].to]&&dis[edge[j].to]>dis[u.Se]+edge[j].w){//判断标记和松弛操作 
				dis[edge[j].to]=dis[u.Se]+edge[j].w;//松弛 
				q.push(P(dis[edge[j].to],edge[j].to));//入队 
			}
		}
	}
} 
int main(){
	
	ini();
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1,u,v,w;i

最小生成树

Kruskal

#include 
using namespace std;
#define N 5001
#define M 200001
struct node{
	int u,v,w;
}edge[M];
int fa[N],n,m;
int find(int x){//并查集找爸爸 
	return fa[x]==x?x:fa[x]=find(fa[x]);
} 
void un(int x,int y){//并查集连接 
	x=find(x);
	y=find(y);
	fa[x]=y;
}
void ini(){//初始化 
	for(int i=1;i

排序

归并排序（求逆序对）

#include
using namespace std;
int n;
int ans=0;
int v[500001];
int t[500001];
void Qsort(int l,int r){//归并 
	if(l==r)return ;
	int mid=(l+r)>>1;
	Qsort(1,mid);
	Qsort(mid+1,r);//递归 
	int i=l;int j=mid+1;int k=l;
	while(i

数据结构

树状数组（区间查询，区间修改）

#include
using namespace std;
int a[500001],b[500001],c[500001];
int n,m;
int lowbit(int x){
	return x&(-x);
}
void updata(int i,int k){
	int x=i;
	while(i0){
		sum+=x*c[i]-b[i];
		i-=lowbit(i);
	}
	return sum;
}
//1：区间修改，2：区间查询 
int main(){
	
	scanf("%d%d",&n,&m);
	for(int i=1;i

考前算法总结

标签：printf   ems   lowbit   next   +=   c++   priority   初始   jks   

原文地址：https://www.cnblogs.com/binghun/p/13924146.html