常用算法模板程序集锦
- 并查集模板函数
int a[100];
//初始状态，每个点的父亲是自己或者0，即每个点各是一个集合。
int InitSet(int MemberNum)
{
for(int i=0;i<MemberNum;i++)
a[i]=i;
/*
for(int i=0;i<=MemberNum-1;i++)
a[i]=0;
*/
}
int rootfind(int x)
{
if(a[x]==x)
return (x);
else
a[x]=rootfind(a[x]);
return (a[x]);
//或者 return(a[x]==x?x:a[x]=rootfind(a[x]))
}
//合并两个根节点，即合并两个集合。先找根节点，在调用此函数，
//也可以不用函数
void UnionRoot(int r1,int r2)
{
a[r2] = r1;
}
2．最短路径问题
2.1迪杰斯特拉算法
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct Edge{
int to,w;
};
vector<Edge>E[1010];//下标从1开始
int dist[1010];//下标从1开始
bool used[1010];//下标从1开始
const int MAX=1000000010;
int main()
{
int i,j,u,v,t,n,m,s;
scanf(“%d%d%d”,&n,&m);
for(i=1;i<=m;i++)
{
scanf(“%d%d%d”,&u,&v,&t);
E[u].push_back((Edge){v,t});
E[v].push_back((Edge){u,t});
//有向图版：E[u].push_back((Edge){v,t});
//无向图要存两条边
}
for(i=1;i<=n;i++)
dist[i]=MAX;
dist[1]=0;//源点为1
int k,min;
for(i=0;i<n-1;i++)//迪杰斯特拉算法，这里控制循环次数，必须保证n-1次循环
{
//在没确定最短路径的点中寻找路径最短的点，将它作为下一步的中转点
min=MAX;
for(j=1;j<=n;j++)
if(min>dist[j] && used[j]==0)
{
k=j;
min=dist[j];
}
s=k;
used[s]=1;
//松弛
for(j=1;j<E[s].size();j++)
dist[E[s][j].to]=min(dist[E[s][j].to],dist[s]+E[s][j].w);
}
printf(“%d”,dist[n]);
}
2.2迪杰斯特拉算法优化
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N=100010;
struct Edge{int to,len;};
vector <Edge> E[N];
int n,m;
long long dist[N];
bool used[N];
struct Point{
int no;
long long dist;
friend bool operator > (const Point A, const Point B){
return A.dist!=B.dist?A.dist>B.dist:A.no>B.no;
}
};
priority_queue <Point, vector<Point>, greater<Point> > Q;
void Dijk(int st){
memset(dist, 0x3f, sizeof(dist));
dist[st]=0ll;
Q.push((Point){st,0ll});
while(!Q.empty()){
int now=Q.top().no;
Q.pop();
if(used[now]) continue;
used[now]=1;
for(int i=0;i<E[now].size();i++){
if(dist[E[now][i].to]>dist[now]+E[now][i].len){
dist[E[now][i].to]=dist[now]+E[now][i].len;
Q.push((Point){E[now][i].to, dist[E[now][i].to]});
}
}
}
}
int main(){
int S;
scanf(“%d%d%d”, &n,&m,&S);
for(int i=0;i<m;i++){
int s,t,d;
scanf(“%d%d%d”, &s,&t,&d);
E[s].push_back((Edge){t,d});
}
Dijk(S);
for(int i=1;i<=n;i++) printf(i<n?”%lld “:”%lld\n”, dist[i]);
return 0;
}
2.3
弗洛伊德算法
#include <iostream>
using namespace std;
const int INF=99999999;
int N, M, dist[1010][1010];
void floyd(){
for(int k=1;k<=N;k++)
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
int main(){
scanf(“%d %d”, &N, &M);
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
dist[i][j]=(i==j?0:INF);
for(int i=0;i<M;i++){
int s,t,d;
scanf(“%d %d %d”, &s, &t, &d);
dist[s][t]=min(dist[s][t], d);
}
floyd();
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
printf(j<N?”%d “:”%d\n”, dist[i][j]);
return 0;
}