图

有向图的拓扑排序（用来判环）

定义

将有向图中的顶点以线性方式进行排序。即对于任何连接自顶点u到顶点v的有向边uv，在最后的排序结果中，顶点u总是在顶点v的前面。

存在条件

如果存在环，那么就不可能满足u->v时u总是在v的前面了。所以必须是有向五环图（DAG）才能拓扑排序。

是否唯一

如果该DAG任意两个顶点都有确定的关系，拓扑排序就是唯一的。如果有这么一个唯一的拓扑排序，容易知道这样的顺序恰好能够遍历全图且每个顶点只经过一次，我们把这样的路径叫做哈密顿路径。

Kahn算法

维护一个入度为0的集合S，每次从S中取出一个点放入存储答案的L数组，检查该点出发的所有边及连接的点，从图中移除这些边，如果连接的点在删除这条边以后入度变为0，将它加入到集合S中。 如此循环，直到集合S中没有点为止，检查图上还有没有边存在，如果有就存在环，如果没有L数组中存储的就是拓扑排序的结果。 集合S可以用栈实现。

#include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <vector> using namespace std; int in[100100],n,m; priority_queue<int> s; vector<vector<int> > edge(100010); vector<int> ans; void Kahn(){ while(!s.empty()){ int cur=s.top(); s.pop(); ans.push_back(cur); printf("%d ",cur); vector<int> :: iterator it; for(it=edge[cur].begin();it!=edge[cur].end();it++){ in[*it]--; if(!in[*it]){ s.push(*it); } } } } int main(){ memset(in,0,sizeof(in)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); edge[x].push_back(y); in[y]++; } for(int i=1;i<=m;i++){ if(in[i]==0) { s.push(i); //printf("%d ",i); } } Kahn(); return 0; }

例题：奇怪的数列

编程输入3个整数n，p，q，寻找一个由整数组成的数列（a1，a2，……，an），要求：其中任意连续p项之和为正数，任意连续q项之和为负数。0

输入格式

仅一行分别表示n，p，q，之间用一个空格隔开。

输出格式

只有一行，有解即输出这个数列，每个数之间用一个空格隔开。否则输出NO。

思路

用数组S[i]代表前缀和 那么第k位数到第k+p-1位数的和就是S[k+p-1]-S[k-1]>0，可得S[k+p-1]>S[k-1] 同理S[k+q-1]-S[k-1]<0->S[k-1]>S[k+q-1] 如果S[j]>s[k]就从j->k连一条边，拓扑排序若有环则无解，否则拓扑序就是答案。

练习题：VIJOS 1790

题解戳这里

#include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <vector> using namespace std; int in[100100],n,m,clock,ou[100100]; priority_queue<int> s; vector<vector<int> > edge(100010); vector<int> ans; void Kahn(){ while(!s.empty()){ int cur=s.top(); s.pop(); ans.push_back(cur); ou[cur]=clock--; //printf("%d ",cur); for(int i=0;i<edge[cur].size();i++){//vector遍历范式 in[edge[cur][i]]--; if(!in[edge[cur][i]]){ s.push(edge[cur][i]); } } } } int main(){ memset(in,0,sizeof(in)); scanf("%d%d",&n,&m); clock=n; for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); edge[y].push_back(x); in[x]++; } for(int i=1;i<=n;i++){ if(in[i]==0) { s.push(i); //printf("%d ",i); } } Kahn(); for(int i=1;i<=n;i++) printf("%d ",ou[i]); return 0; }

有向图的关键路径

欧拉图

最小生成树

Prim算法

维护一个点集P{}存放已经加入生成树的点，维护一个边集E1{}【使用优先队列，以边权排序】存放所有与点集P中的点相连而没有加入生成树的边，维护边集E2{}存放已经加入生成树的边。 算法流程如下：

随意选一个顶点u加入P，以P为起点更新E1E1.top()取出边(u,v)：如果v还没有被访问过，把该边放入E2，将v加入P，E1.pop()；否则直接E1.pop()，返回该步骤的起点。以v为起点更新E1，返回第二步循环，直至所有顶点都加入了P为止（计数达到顶点数就停止循环）

练习题：VIJOS 1190

这里要转个弯，因为两种最小生成树算法（Prim&Kruskal）都是贪心算法，每次都在选取边权最小的边加入生成树，所以天然满足“最大边权最小”的条件。【证明：如果所求解不是最小生成树，必然会有一条边的边权与最小生成树不同，如果该边权比最小生成树中的小，在选择加入生成树时就会选它而不是边权更大的边，证毕。】然后求解最小生成树即可。

#include <cstdio> #include <algorithm> #include <cstring> #define maxn 300+20 using namespace std; struct edge{ int l,r,w; }; bool operator <(const edge &a,const edge &b){ return a.w<b.w; } int fa[maxn],n,m,u,v,c,ans=0; edge g[20100]; int find(int a){ return fa[a] == a ? fa[a] : fa[a]=find(fa[a]); } void Kruskal(){ int cnt=0; sort(g+1,g+m+1); for(int i=1,j=0;i<=m,j<n-1;i++){ int a=g[i].l; int b=g[i].r; if(find(a)!=find(b)){ ans=g[i].w; fa[find(a)]=find(b); j++; } } return; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&c); g[i].l=u; g[i].r=v; g[i].w=c; } for(int i=1;i<=n;i++) fa[i]=i; Kruskal(); printf("%d %d",n-1,ans); }

注意事项

Prim的时间复杂度为O(n^2)，n为图中顶点的个数，与边无关。所以近乎完全图的问题用Prim的效率更高，下面学习适用于稀疏图的复杂度为O(ElogE)的Kruskal算法。

Kruskal算法

将边(u,v)快排，从小到大考察加入生成树，如果u和v还没有相连（不属于同一个连通分量）就将这条边选入生成树，并将u和v所在联通分量合并，直到加入的边数为n-1为止。

关键点：边快排+并查集判断连通分量

并查集（路径压缩）

int fa[mxn];//记录节点x在并查集中的父节点编号 int find(x){ if(fa[x]==x) return fa[x]; else fa[x]=find(fa[x]); }

练习题：VIJOS 1234

题目条件告诉我们，我们要把这个图分成K个子图，这些子图中的边权之和最小。用Kruskal添边时会有一个合并并查集的操作——每添一条边集合就会少一个，所以添N-K条边即可。

#include <cstdio> #include <algorithm> #include <cstring> #define maxn 20000 using namespace std; struct edge{ int l,r,w; }; bool operator <(const edge &a,const edge &b){ return a.w<b.w; } int fa[maxn],n,m,u,v,c,k,ans=0; bool flag=false; edge g[20000]; int find(int a){ return fa[a] == a ? fa[a] : fa[a]=find(fa[a]); } void Kruskal(){ int j=0; sort(g+1,g+m+1); for(int i=1;i<=m;i++){ int a=g[i].l; int b=g[i].r; if(find(a)!=find(b)){ ans+=g[i].w; fa[find(a)]=find(b); j++; } if(j>=n-k) { flag=true;break; } } } int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&c); g[i].l=u; g[i].r=v; g[i].w=c; } for(int i=1;i<=n;i++) fa[i]=i; Kruskal(); if(flag) printf("%d",ans); else printf("No Answer"); return 0; }

单源最短路

只有当图不存在负权回路时才有单源最短路

Dijkstra算法（不带负边权，O(n^2)）

dist[j]记录从出发点i到j的最短距离，如果i->j有边相连，初始化时就赋值为边权，否则为+∞以dist[j]为依据将其余顶点加入一优先队列，每次从中取dist[j]最小的点（dist[i]=0），vis[j]标记为true以表示该点至源点的最短路径已经求得从j出发考察与j相连的所有（vis[v]==false的）点v，如果dist[v]>dist[j]+dist[j,v]就更新dist[v]为dist[j]+dist[j,v]重复2、3直至所有点都vis==true

SPFA算法（带负边权，O(ke)）

负权回路

如果图中存在负权回路，就不可能有最短路了（越走越小…），用SPFA算法统计入队次数可以很容易判断图中是否有负权回路。方法有两种：

总的点入队次数大于点数的两倍单个点的入队次数大于sqrt(总的点数)

算法描述

将源点s加入队列，dist[s]=0，其余dist=+∞在更新点时使用队列，每次从队列中取出一个节点u对其相邻节点v进行松弛（relax）操作——如果dist[v]>dist[u]+dist[v,u]，更新dist[v]并将v加入队列反复2直至队列为空或者判断出图中有负权回路

练习题：VIJOS 1754

练习题：VIJOS 1050

练习题：VIJOS 1119

练习题：VIJOS 1591

所有点对之间最短路

Floyd算法（动态规划）

void Floyd(){ for(int k=1;i<=n;i++) for(int i=1;j<=n;j++) for(int j=1;k<=n;k++) if(dist[i][j]>dist[i][k]+dist[k][j]) dist[i][j]=dist[i][k]+dist[k][j]; return; }

练习题：VIJOS 1746

转载于:https://www.cnblogs.com/leotan0321/p/6081365.html

相关资源：各显卡算力对照表！