下面是关于图的一些模板。
一、最短路
1、Floyed
void floyed()//O(N^3) { for (int k=1;k<=n;k++)//中间点 for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j]; }
2、Dijkstra
void dijkstra()//O(N^2) { memset(vis,false,sizeof(vis)); memset(dis,0x3f3f3f3f,sizeof(dis));//从st到i节点的距离 dis[st]=0;pre[st]=0;//pre:记录路径 for (int i=1;i<=n;i++) { int mi=INF,cur=0; for (int j=1;j<=n;j++)//找到一个最近的没被访问的点进行更新 if (!vis[j]&&dis[j]<mi){ mi=dis[j]; cur=j; } if (cur==0) break; vis[cur]=true; for (int j=he[cur];j;j=ne[cur])//更新cur所连接的没有访问的点 if (!vis[to[j]]&&dis[to[j]]>dis[cur]+w[j]){ dis[to[j]]=w[j]+dis[cur];//in add:he[],ne[],w[] pre[to[j]]=cur; } } }
3、SPFA (注意与BFS的区别)
void SPFA()//O(kE) k常数 { memset(dis,0x3f3f3f3f,sizeof(dis)); memset(vis,false,sizeof(vis)); queue<int> q; dis[st]=0;vis[st]=true;q.push(st); while (!q.empty()) { int u=q.front();q.pop(); vis[u]=false;//differ from BFS for (int i=he[u];i;i=ne[i]) if (dis[to[i]]>dis[u]+w[i]){//*** dis[to[i]]=dis[u]+w[i]; pre[to[i]]=u;//路径 if (!vis[to[i]]){//***differ from BFS vis[to[i]]=true; q.push(to[i]); } } } }
二、图的连通性
1、Floyed
void floyed() { for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) dis[i][j]=dis[i][j]||(dis[i][k]&&dis[k][j]); }
2、DFS (就不写了)
三、图_并查集
int find_fa(int x)//找爸爸及递归压缩路径 { if (fa[x]!=x) return fa[x]=find_fa(fa[x]); return fa[x]; } void unionn(int a,int b)//合并爸爸，可以不写函数 { fa[b]=a; } void workk() { //pre 赋初值 for (int i=1;i<=n;i++) fa[i]=i; //add 加关系 for (int i=1;i<=m;i++)//边 { int x,y; scanf("%d%d",&x,&y); int r1=find_fa(x); int r2=find_fa(y); if (r1!=r2) unionn(r1,r2); } //query 查询 for (int i=1;i<=q;i++) { int x,y; scanf("%d%d",&x,&y); if (find_fa(x)!=find_fa(y)) printf("yes "); else printf("no "); } }
四、图_最小生成树
1、Kruskal
struct pp{ int st,en,w;//一条边连接的两个点及边的权值 }; pp v[105]; int find(int x) { if (fa[x]!=x) return fa[x]=find(fa[x]); return fa[x]; } const int comp(const pp&a,const pp&b) { return a.w<b.w; } void kruskal()//O(E*logE) { //pre for (int i=1;i<=n;i++) fa[i]=i; int ans=0;//最小生成树长度 int k=0;//已经找到了多少条边 sort(v+1,v+1+m.comp);//v：结构体存边，m边数 ,边按小到大排序 for (int i=1;i<=m;i++) { if (find(v[i].st)!=find(v[i].en)) { int r1=v[i].st; int r2=v[i].en; if (r1!=r2) fa[r2]=r1; ans+=v[i].w; k++; } if (k==n-1) break; } }