1.堆优化的dij
priority_queue<Type, Container, Functional>
Type为数据类型， Container为保存数据的容器，Functional为元素比较方式。
如果不写后两个参数，那么容器默认用的是vector，比较方式默认用operator<，也就是优先队列是大顶堆，队头元素最大。
#include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int maxn=1e5+10; typedef pair<int,int> PII; int head[maxn],nex[maxn],ver[maxn],wei[maxn],tot; int n,m; priority_queue<PII,vector<PII>,greater<PII>> q;//这里要设置成PII int dis[1000]; bool st[1000]; inline void add(int x,int y,int w) { ver[++tot]=y; wei[tot]=w; nex[tot]=head[x]; head[x]=tot; } inline void dij() { q.push({0,1}); memset(dis,0x3f,sizeof(dis)); dis[1]=0; while(q.size()) { auto t=q.top(); q.pop(); int x=t.second,d=t.first; if(st[x]) continue; st[x]=true; for(int i=head[x];i;i=nex[i]) { int y=ver[i]; if(dis[y]>d+wei[i])//如果有的话就更新 { dis[y]=d+wei[i]; q.push({dis[y],y}); } } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); } dij(); if(dis[n]==0x3f3f3f3f) printf("-1");//四组3f else printf("%d",dis[n]); return 0; }
请注意，dij的适用范围是非负权回路（所以有0边是可以实现的）
2.spfa:处理带有负权边和环的最短路算法
#include <stdio.h> #include <algorithm> #include <cstring> #include <queue> #include <cctype> using namespace std; const int maxn=1e5+10; int head[maxn],nex[maxn],wei[maxn],ver[maxn],tot; int n,m; bool st[maxn]; int dis[maxn]; queue<int>q; inline int read() { int x=0,b=1;char c=getchar(); while(!isdigit(c)) b=c==‘-‘?-1:1,c=getchar(); while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x*b; } inline void add(int x,int y,int w) { ver[++tot]=y; wei[tot]=w; nex[tot]=head[x]; head[x]=tot; } inline void spfa() { q.push(1); memset(dis,0x3f,sizeof(dis)); dis[1]=0; st[1]=true; while(q.size()) { int x=q.front(); q.pop(); st[x]=false; for(int i=head[x];i;i=nex[i]) { int y=ver[i]; if(dis[y]>dis[x]+wei[i]) { dis[y]=dis[x]+wei[i]; if(!st[y]) { st[y]=true; q.push(y); } } } } } int main() { n=read(),m=read(); for(int i=1;i<=m;i++) { int a,b,c; a=read(),b=read(),c=read(); add(a,b,c); } spfa(); // for(int i=1;i<=n;i++) printf("%d ",dis[i]); if(dis[n]==0x3f3f3f3f) printf("impossible"); else printf("%d",dis[n]); return 0; }
2.1适用spfa算法判断负环：
#include <stdio.h> #include <algorithm> #include <cstring> #include <queue> #include <cctype> using namespace std; const int maxn=1e5+10; int head[maxn],nex[maxn],wei[maxn],ver[maxn],tot; int n,m; bool st[maxn]; int dis[maxn],cnt[maxn]; queue<int>q; inline int read() { int x=0,b=1;char c=getchar(); while(!isdigit(c)) b=c==‘-‘?-1:1,c=getchar(); while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x*b; } inline void add(int x,int y,int w) { ver[++tot]=y; wei[tot]=w; nex[tot]=head[x]; head[x]=tot; } inline bool spfa() { for(int i=1;i<=n;i++) { st[i]=true; q.push(i); } while(q.size()) { int x=q.front(); q.pop(); st[x]=false; for(int i=head[x];i;i=nex[i]) { int y=ver[i]; if(dis[y]>dis[x]+wei[i]) { dis[y]=dis[x]+wei[i]; cnt[y]=cnt[x]+1; if(cnt[y]==n) return true; if(!st[y]) { st[y]=true; q.push(y); } } } } return false; } int main() { n=read(),m=read(); for(int i=1;i<=m;i++) { int a,b,c; a=read(),b=read(),c=read(); add(a,b,c); } if(spfa()) printf("Yes"); else printf("No"); // for(int i=1;i<=n;i++) printf("%d ",dis[i]); return 0; }
3.最近公共祖先：
3.1倍增求lca（预处理O（nlogn）查询O（logn））
3.2离线求lca（感觉没有什么用）trajan求lcaO(n+m)
4.拓扑排序：
#include <stdio.h> #include <algorithm> #include <cstring> #include <iostream> using namespace std; const int maxn=2000; int head[maxn],nex[maxn],ver[maxn],tot; int q[maxn]; int d[maxn]; int n; inline void add(int x,int y) { ver[++tot]=y; nex[tot]=head[x]; head[x]=tot; } inline void topsort() { int hh=0,tt=-1; for(int i=1;i<=n;i++) if(d[i]==0) q[++tt]=i; while(hh<=tt) { int x=q[hh++]; for(int i=head[x];i;i=nex[i]) { int y=ver[i]; if(--d[y]==0) q[++tt]=y; } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int son; while(scanf("%d",&son),son) { add(i,son); d[son]++; } } topsort(); for(int i=0;i<n;i++)printf("%d ",q[i]); return 0; }
注意，q队列实际上也就是拓扑序的队列：
4.1 差分约束问题：（求最长路）【边权无限制】spfaO(km)
如果说所以边权都是非负的：强联通分量求解（有向图trajan）
如果说所有边权都是1的话，就可以使用拓扑排序来求解
原文：https://www.cnblogs.com/ILHYJ/p/13770156.html
