最短路
单源多汇最短路
Dijkstra
基于贪心思想，每次松弛距离起点最近的点（可以用小根堆实现）复杂度为**O(mlogn) ** 正确性：当z>=0时，全局的最小值不可能会被其他点更新，所以在找出的x必然满足:dis[x]已经是起点到x的最短路径，我们不断选择全局最小值进行标记和拓展,最终可以得到起点到每个节点的最短路径的长度
代码如下：
#define P pair<int,int>
priority_queue<P> q;
dis[s]=0;
q.push(P(0,s));
while(!q.empty())
{
int x=q.top().second;
q.pop();
if(v[x])
continue;
v[x]=1;
for(int i=0;i<a[x].size();i++)
{
int y=a[x][i].first,val=a[x][i].second;
if(dis[y]>dis[x]+val)
{
dis[y]=dis[x]+val;
q.push(P(dis[y],y));
}
}
}
Dijkstra算法不能跑负权，这就要用到SPFA（队列优化的Ford算法,不过好像已经死了，但还没死透）复杂度为O(km)但有时会退化到O(nm)。 对于每条边条边(x,y,z),dis[y]<=dis[x]+z成立,则d数组就是所求的最短路
代码如下
queue<int> q;
void spfa()
{
memset(dis,0x3f,sizeof(dis));
q.push(s);
dis[s]=0;
v[s]=1;
while(!q.empty())
{
int x=q.front();
qq.pop();
v[x]=0;
for(int i=0;i<a[x].size();i++)
{
int y=a[x][i].first,val=a[x][i].second;
if(dis[y]>dis[x]+val)
{
dis[y]=dis[x]+val;
if(!v[y])
{
qq.push(y);
v[y]=1;
}
}
}
}
}
多源单汇
直接建反图，再跑单源多汇。
多源多汇
1.Floyd基于dp,时间复杂度为O(\(x^3\))注意中继点在最外层枚举
代码如下：
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
2.跑n遍Dijkstra,复杂度为O(nmlogn),但不能处理负边权
3.Johnson算法
先建一个超级起点，连接上每一个点，跑一边最短路，得到距离s的最短路数组h[i]。
对于任意权值w(x,y)修改成w(x,y)+h[x]-h[y].
正确性证明：
我们需要证明两个东西
1. 修改完边权后的最短路径还是原来的最短路径
对于任意一条路径s->\(p_1\)->\(p_2\)->\(p_3\)->......->t
原权值为w(s,\(p_1\))+w(\(p_1\),\(p_2\))+w(\(p_2\),\(p_3\))+......+w(\(p_k\),t)
修改后为w(s,\(p_1\))+h[s]-h[\(p_1\)]+w(\(p_1\),\(p_2\))+h[\(p_1\)]-h[\(p_2\)]+w(\(p_2\),\(p_3\))+h[\(p_2\)]-h[\(p_3\)]+......+w(\(p_k\),t)+h[\(p_k\)]-h[t]
可以发现中间的权值都被消除最后只剩下w(s,\(p_1\))+w(\(p_1\),\(p_2\))+w(\(p_2\),\(p_3\))+......+w(\(p_k\),t)+h[s]-h[t]
因为图是固定的的，所以h数组是固定的，则h[s]-h[t]为固定的，所以修改完边权后的最短路径还是原来的最短路径
2. 权值为正
因为h数组满足最短路的性质，对于任意w(x,y)都有$ h[y]\leq h[x]+w(x,y) \(所以\) w(x,y)+h[x]-h[y] \geq 0 $，故成立。
代码如下
#include<bits/stdc++.h>
using namespace std;
#define val a[x][i].second
#define to a[x][i].first
#define P pair<int,int>
vector<pair<int,int> > a[3010];
queue<int> qq;
const int N=1e4;
priority_queue<P,vector<P>,greater<P> > q;
long long ans,d[N],dis[N];
int v[N],f[N];
int n,m,x,y,z;
bool spfa()
{
memset(dis,0x3f,sizeof(dis));
qq.push(0);
dis[0]=0;
v[0]=1;
while(!qq.empty())
{
int x=qq.front();
qq.pop();
v[x]=0;
for(int i=0;i<a[x].size();i++)
{
if(dis[to]>dis[x]+val)
{
dis[to]=dis[x]+val;
if(!v[to])
{
qq.push(to);
v[to]=1;
}
f[to]=f[x]+1;
if(f[to]>n+1)
return 0;
}
}
}
return 1;
}
void DIJ(int s)
{
memset(dis,0x3f,sizeof(dis));
memset(v,0,sizeof(v));
dis[s]=0;
q.push(P(0,s));
while(!q.empty())
{
int x=q.top().second;
q.pop();
if(v[x])
continue;
v[x]=1;
for(int i=0;i<a[x].size();i++)
{
if(dis[to]>dis[x]+val)
{
dis[to]=dis[x]+val;
q.push(P(dis[to],to));
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
a[x].push_back(P(y,z));
}
for(int i=1;i<=n;i++)
{
a[0].push_back(P(i,0));
}
if(spfa()==0)
{
cout<<"-1";
return 0;
}
for(int i=1;i<=n;i++)
{
d[i]=dis[i];
}
for(int x=1;x<=n;x++)
{
for(int i=0;i<a[x].size();i++)
{
val+=dis[x]-dis[to];
}
}
for(int i=1;i<=n;i++)
{
DIJ(i);
ans=0;
for(int j=1;j<=n;j++)
{
if(dis[j]>=0x3f3f3f3f)
ans+=j*1e9;
else
ans+=j*(dis[j]-d[i]+d[j]);
}
cout<<ans<<endl;
}
return 0;
}
一个神奇(没什么用)的优化
线段树优化的Dijkstra
因为优先队列虽然确实是优化了，但是常数还是很大的。其作用也就是返回区间的最小值，并且如果用过了就弹出去。这就可以用线段树维护，而且常数远小于优先队列。开一个ans数组存答案，再开一个线段树支持查询和修改,因为每个点只需取一次，所以用过后要将它改为INF覆盖掉。
还是快的挺多的。
还有一种写法，用树状数组维护区间最值，请自行百度，我没写
最短路径树
从一张连通图中，有树满足从根节点到任意点的路径都为原图中根到任意点的最短路径的树。最短路径树是一棵生成树，这里我们使用Dijkstra来实现。记录pre数组为点x的前驱，pre记录的是边，对于每次比较，如果d[y]==d[x]+z。则证明该边是最短路上的一条边，我们要保证边权和最小就要比较edge[pre[x]]和edge[i]，如果edge[i]<edge[pre[x]]，更新pre[x]为i。
只要在Dijkstra比较时加入
if(edge[i]+d[x]==d[y]&&edge[i]<edge[pre[y]])
pre[y]=i;
例题时间
-
Johnson的板子题,直接写
-
注意有重边和自环。
设a[x]为起点到x的最短路的个数
对于遍历到的每条边，有两种情况
（1）d[x]+z==d[y]
我们可以直接让a[y]+=a[x]。
（2）d[x]+z>d[y]
可以直接a[y]=a[x]因为y之前的最短路的值已经不是最优，要替换
代码
#include<iostream> #include<queue> #include<cstdio> #include<cstring> #include<vector> using namespace std; typedef pair<int,int> P; priority_queue<P,vector<P>,greater<P> > q; const int N=1000100; const int mod=100003; vector<int> a[N]; int x,y,z; int tot,n,m,s,v[N],d[N],ans[N]; void DIJ() { memset(d,0x3f,sizeof(d)); d[s]=0; q.push(P(d[s],s)); while(!q.empty()) { int x=q.top().second; q.pop(); if(v[x]==1) continue; else v[x]=1; for(int i=0;i<a[x].size();i++) { int y=a[x][i]; int z=1; if(d[x]+z==d[y]) ans[y]+=ans[x],ans[y]%=mod; if(d[x]+z<d[y]) ans[y]=ans[x],ans[y]%=mod; if(d[x]+z<=d[y]) { d[y]=d[x]+z; q.push(P(d[y],y)); } } } } int read() { int x = 0, f = 1, ch = getchar(); while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); return x * f; } int main() { n=read();m=read();s=1; for(int i=1;i<=m;i++) { x=read();y=read(); a[x].push_back(y); a[y].push_back(x); } ans[1]=1; DIJ(); for(int i=1;i<=n;i++) { if(d[i]==0x3f3f3f3f) printf("0\n"); else printf("%d\n",ans[i]%mod); } return 0; } -
P3106 [USACO14OPEN]Dueling GPSs S
题意：给你一张有向图，可能有重边，现有两个GPS，他们经过相同路径的边权不同
当每走一条边，如果一个系统认为走的这条边不是它认为的最短路,就会受到一次警告，警告可叠加
如果边(x,y)不在u到n的最短路径上，就要受到一次警告，问：从1到n最少受到多少次警告
解法：因为不在u到n的最短路径，会受到警告，所以要建反图
跑三次最短路，第一次，以GPS1的边权跑，得出第一个的最短路径，再以GPS2的边权跑，得出第二个最短路径。对于一条边，如果他是某个最短路径中的一条边，他一定满足d[x]+z==d[y]，所以如果一条边满足GPS1的最短路径，则num++，如果满足GPS2的最短路径，则num++，以num为边的边权，再跑最短路，最后d[1]即为答案
代码
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> P; priority_queue<P,vector<P>,greater<P> > q; const int N=5e4+100; int tot,n,m; int u[N],v[N],val_a[N],val_b[N],dis_a[N],dis_b[N],dis_c[N]; int edge[N],head[N],ver[N],nxt[N],vis[N]; int read() { int x = 0, f = 1, ch = getchar(); while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); return x * f; } void add(int x,int y,int z) { ver[++tot]=y; edge[tot]=z; nxt[tot]=head[x]; head[x]=tot; } void Dij(int s,int *dis) { memset(vis,0,sizeof(vis)); dis[s]=0; vis[s]=0; q.push(P(dis[s],s)); while(!q.empty()) { int x=q.top().second; q.pop(); if(vis[x]) continue; vis[x]=1; for(int i=head[x];i;i=nxt[i]) { int y=ver[i],z=edge[i]; if(dis[y]>=dis[x]+z) { dis[y]=dis[x]+z; q.push(P(dis[y],y)); } } } } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { v[i]=read();u[i]=read(); val_a[i]=read();val_b[i]=read(); } for(int i=1;i<=m;i++) { add(u[i],v[i],val_a[i]); } memset(dis_a,0x3f,sizeof(dis_a)); Dij(n,dis_a); memset(head,0,sizeof(head)); tot=0; for(int i=1;i<=m;i++) { add(u[i],v[i],val_b[i]); } memset(dis_b,0x3f,sizeof(dis_b)); Dij(n,dis_b); memset(head,0,sizeof(head)); tot=0; for(int i=1;i<=m;i++) { int num=0; if(dis_a[u[i]]+val_a[i]!=dis_a[v[i]]) num++; if(dis_b[u[i]]+val_b[i]!=dis_b[v[i]]) num++; add(u[i],v[i],num); } memset(dis_c,0x3f,sizeof(dis_c)); Dij(n,dis_c); printf("%d\n",dis_c[1]); return 0; } -
出题人贴心的把时间保证单调不降，题意就是说在t之前修建好的村庄都可以作为中继点。中继点的思想很像Floyd，那么我们就可以对于每次要修好的村庄，在原来图的基础上，再跑一次Floyd即可
代码
#include<bits/stdc++.h> using namespace std; int f[210][210],t[210]; int x,y,n,m,u,v,w,q,tt; int read() { int f=1,x=0,ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return f*x; } int main() { memset(f,0x3f,sizeof(f)); n=read();m=read(); for(int i=0;i<n;i++) t[i]=read(); for(int i=1;i<=m;i++) { u=read();v=read();w=read(); f[u][v]=w; f[v][u]=w; } q=read(); int now=0; for(int i=1;i<=q;i++) { x=read();y=read();tt=read(); while(t[now]<=tt&&now<n) { for(int st=0;st<n;st++) { for(int ed=0;ed<n;ed++) { f[ed][st]=f[st][ed]=min(f[st][ed],f[st][now]+f[now][ed]); } } now++; } if(t[x]>tt||t[y]>tt||f[x][y]==0x3f3f3f3f) printf("-1\n"); else printf("%d\n",f[x][y]); } return 0; }问：那可以用Dij水过去吗？可以，请左转题解第5篇，好像很麻烦
-
一道差分约束的题，对于差分约束，我们要将题目给的式子转化成约束条件，有些会隐藏在题目中
对于这道题我们设d[i]为0~i之间至少选择多少数，所以d[b[i]]-d[a[i]-1]>=c[i]，对于一个数我们可以选或不选，即d[i]-d[i-1]>=0,d[i]-d[i-1]<=1(d[i-1]-d[i]>=-1)注意若从0开始i-1可能为负，所以将所有的下标都加1
代码
#include<bits/stdc++.h> using namespace std; queue<int> q; const int N=50010; int n,a,b,c,v[N],d[N],T; int tot=0,edge[N*4],nxt[N*4],ver[N*4],head[N]; int read() { int x=0,f=1,ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); } return x*f; } void add(int x,int y,int z) { ver[++tot]=y; edge[tot]=z; nxt[tot]=head[x]; head[x]=tot; } void SPFA(int s) { memset(d,0xcf,sizeof(d)); memset(v,0,sizeof(v)); q.push(s); d[s]=0; v[s]=1; while(!q.empty()) { int x=q.front(); q.pop(); v[x]=0; for(int i=head[x];i;i=nxt[i]) { int y=ver[i],z=edge[i]; if(d[x]+z>d[y]) { d[y]=d[x]+z; if(!v[x]) { q.push(y); v[y]=1; } } } } } int main() { T=read(); for(int t=1;t<=T;t++) { memset(head,0,sizeof(head)); tot=0; n=read(); int maxn=0; for(int i=1;i<=n;i++) { a=read();b=read();c=read(); add(a,b+1,c); maxn=max(maxn,b+1); } for(int i=1;i<=maxn;i++) { add(i,i+1,0); add(i+1,i,-1); } SPFA(1); printf("%d\n",d[maxn]); } } -
双倍的快乐？UVA 1723 Intervals的确，但这道题的输出有些不大一样，注意对于每两个输出之间还要有换行，但最后一个输出只能有一个换行
-
给一张图无向图，两个人，起点不同，终点不同，求两个人的最大重合路径
和。
和3题差不多，不过要跑4遍最短路，分别以两个起点和终点为起点，跑最短路。要求重合路径，所以判断一条边是否在公共最短路上，如果在，就建一个新图，再跑最长路，不知为何我的Dij求最长路出锅了，因为是有向图，不具有后效性，所以我们用dp来解决,我们设入度为0的点的d数组为0（也可以设出度为0的d数组为0）即一条路的两端dp[x]=max(dp[x],dfs(y)+z);dfs递归找d[y]，加上记忆化搜索
代码
#include <iostream> #include <cstring> #include <queue> #include <climits> using namespace std; #define P pair<int,int> priority_queue<P,vector<P>,greater<P> > q; struct ed{ int v,next,w; }e[5000000],e2[5000000]; int st,dis_a[50000],dis_b[5000],dis_c[5000],dis_d[5000]; int fir[10000],fir1[10000],fir2[20000],dp[10000],maxx; int n,m,u,v,l,x,xx,y,yy,rd[10000],tot; bool vis[40000]; void add(int u,int v,int l) { e[++tot].v=v; e[tot].next=fir[u]; e[tot].w=l; fir[u]=tot; } void add2(int u,int v,int l) { e2[++tot].v=v; e2[tot].next=fir2[u]; e2[tot].w=l; fir2[u]=tot; rd[u]=rd[v]=1; } int dfs(int u) { if (dp[u]) return dp[u]; for (int i=fir2[u];i;i=e2[i].next) { int v=e2[i].v,w=e2[i].w; dp[u]=max(dp[u],dfs(v)+w); } return dp[u]; } void DIJ(int s,int *dis) { for(int i=1;i<=n;i++) { dis[i]=0x7f7f7f7f; vis[i]=0; } dis[s]=0; vis[s]=0; q.push(P(dis[s],s)); while(!q.empty()) { int x=q.top().second; q.pop(); if(vis[x]) continue; vis[x]=1; for(int i=fir[x];i;i=e[i].next) { int y=e[i].v,z=e[i].w; if(dis[y]>dis[x]+z) { dis[y]=dis[x]+z; q.push(P(dis[y],y)); } } } } int main() { cin>>n>>m; cin>>x>>y>>xx>>yy; for (int i=1;i<=m;i++) cin>>u>>v>>l,add(u,v,l),add(v,u,l); DIJ(x,dis_a); DIJ(y,dis_b); DIJ(xx,dis_c); DIJ(yy,dis_d); tot=0; for(int i=1;i<=n;i++) { for(int j=fir[i];j;j=e[j].next) { int ya=e[j].v,w=e[j].w; if(dis_a[i]+w+dis_b[ya]==dis_a[y]) { if(dis_c[i]+w+dis_d[ya]==dis_c[yy]) add2(i,ya,w); if(dis_c[ya]+w+dis_d[i]==dis_c[yy]) add2(ya,i,w); } } } memset(dp,0,sizeof(dp)); for (int i=1;i<=n;i++) if (rd[i]&&!dp[i]) dfs(i); for (int i=1;i<=n;i++) maxx=max(maxx,dp[i]); cout<<maxx<<endl; return 0； }最短路径树习题
CF545E Paths and Trees
给一张无向图和起点，求最短路径树的边权和，并输出边的编号
就是直接套板子，我们想想如何输出边。跑完最短路后，我们的pre数组所指的边就是我们要的边，我们找到每个点的pre数组并将其记录，注意是无向图，所以我们要向上取整如1和2代表一条边的不同方向(x+1)/2当x=1或x=2是都为1。
注意：d数组的初值一定要设很大，WA了好几次
代码
#include<bits/stdc++.h> using namespace std; #define P pair<long long,int> priority_queue<P,vector<P>,greater<P> > q; const int N=3000100; int pre[N],head[N],nxt[N],ver[N],v[N]; int s,n,m,x,y,z,tot; long long d[N],ans,id[N],num,edge[N]; void add(int x,int y,int z) { ver[++tot]=y; edge[tot]=z; nxt[tot]=head[x]; head[x]=tot; } void DIJ(int s) { for(int i=1;i<=n;i++) { d[i]=0x3f3f3f3f3f3f3f3f; v[i]=0; } q.push(P(0,s)); d[s]=0; while(!q.empty()) { int x=q.top().second; q.pop(); if(v[x]) continue; v[x]=1; for(int i=head[x];i;i=nxt[i]) { int y=ver[i],z=edge[i]; if(d[x]+z<d[y]) { d[y]=d[x]+z; if(!v[y]) q.push(P(d[y],y)); pre[y]=i; } if(edge[i]+d[x]==d[y]&&edge[i]<edge[pre[y]]) pre[y]=i; } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } scanf("%d",&s); DIJ(s); for(int i=1;i<=n;i++) { if(i==s) continue; int k=pre[i]; ans+=edge[k]; id[++num]=k; } printf("%lld\n",ans); for(int i=1;i<=num;i++) { printf("%lld ",(id[i]+1)/2); } return 0; }CF1076D Edge Deletion
给一张无向图，要求删边，使图最多剩下k条边，且获得最多的好点。定义“好点”是指删边后, 1号节点到它的最短路长度仍然等于原图最短路长度的节点。即最短路径树上的点
输出保留的边数和保留的边的编号
如果k>=n-1，那么就是最短路径树的板子。
但当k<n-1时，我们就要考虑删掉哪些边和舍弃哪些点并保持图的连通性。我们直接DFS当该条边为pre数组中的边时直接往下DFS。
代码：
#include<bits/stdc++.h> using namespace std; #define P pair<long long,int> priority_queue<P,vector<P>,greater<P> > q; const int N=3000100; int pre[N],head[N],nxt[N],ver[N],v[N]; int s,n,m,x,y,z,tot,t; long long d[N],ans,id[N],num,edge[N]; int read() { int x=0,f=1,ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); } return x*f; } void add(int x,int y,int z) { ver[++tot]=y; edge[tot]=z; nxt[tot]=head[x]; head[x]=tot; } void DFS(int x,int fa) { if(num==t) return; for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(y==fa) continue; if(pre[y]==i) { num++; printf("%d ",(i+1)/2); DFS(y,x); if(num>=t) return; } } } void DIJ(int s) { for(int i=1;i<=n;i++) { d[i]=0x3f3f3f3f3f3f3f3f; v[i]=0; } q.push(P(0,s)); d[s]=0; while(!q.empty()) { int x=q.top().second; q.pop(); if(v[x]) continue; v[x]=1; for(int i=head[x];i;i=nxt[i]) { int y=ver[i],z=edge[i]; if(d[x]+z<d[y]) { d[y]=d[x]+z; if(!v[y]) q.push(P(d[y],y)); pre[y]=i; } if(edge[i]+d[x]==d[y]&&edge[i]<edge[pre[y]]) pre[y]=i; } } } int main() { n=read(); m=read(); t=read(); for(int i=1;i<=m;i++) { x=read();y=read();z=read(); add(x,y,z);add(y,x,z); } DIJ(1); int f=min(n-1,t); printf("%d\n",f); DFS(1,0); return 0; }