摘要
本文接上文 最短路算法，为大家介绍最短路的常见应用。
将原来打的各种题目的零散文章汇总，编入精选文章。
负环与差分约束
一个看起来不像最短路的最短路应用。给出一组差分约束，问是否有解。差分约束是形容 或 的式子。可以将这样的式子转化为 的形式。这就像一个松弛操作的式子。我们的目标是找到合适的 使得 ，若 分别表示一个图中的最短路长度，那么这个式子的含义就是 无法从 松弛！
因此可以把 转化为 的形式，表示结点 j 向结点 i 连一条权值为 a 的边。 同理。然后对这个图求一个最短路即可。
何时无解？当出现负环时。
判断负环，常用 SPFA 的 DFS 变种算法，其实质就是 DFS 更新（原 SPFA 是类似 BFS 更新）
[LG1993] 小 K 的农场
对于一组变量 ，给定 m 个如下三种条件：
- .
- .
- .
求是否存在满足所有条件的一组 .
设农场 的作物数为 。对于 ，变形为 ，即松弛不等式。因此，从 向 连一条长度为 的边。对于这个差分约束图求最短路。如果有负环，则无解，否则有解。
对于 ，转化为 即可；对于 ，建 0 边即可。
spfaDFS 判负环。设置一个结点 0，将所有点都建 0 边，使图连通。
坑：空间要开够
#include<cstdio>
#include<cstring>
using namespace std;
const int N=10004;
int n,m;
struct qxx{int nex,t,v;};
qxx e[N*2];
int h[N],cnt;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}
int vis[N],d[N];//cnt 记录到 i 的最短路的边数
bool spfa(int u){vis[u]=1;
for(int i=h[u];i;i=e[i].nex){
if(d[e[i].t]>d[u]+e[i].v){
d[e[i].t]=d[u]+e[i].v;
if(vis[e[i].t])return 0;// 环
if(!spfa(e[i].t))return 0;
}
}
vis[u]=0;
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int o,a,b,c;
scanf("%d%d%d",&o,&a,&b);
if(o==1)scanf("%d",&c),add_path(a,b,-c);
else if(o==2)scanf("%d",&c),add_path(b,a,c);
else add_path(a,b,0),add_path(b,a,0);
}
for(int i=1;i<=n;i++)add_path(0,i,0),d[i]=0x3f3f3f3f;
puts(spfa(0)?"Yes":"No");
return 0;
}
[LG3084] 照片 Photo
农夫约翰决定给站在一条线上的 头奶牛制作一张全家福照片，N 头奶牛编号 1 到 N。
于是约翰拍摄了 张照片，每张照片都覆盖了连续一段奶牛：第 i 张照片中包含了编号 到 的奶牛。但是这些照片不一定把每一只奶牛都拍了进去。
在拍完照片后，约翰发现了一个有趣的事情：每张照片中都有且仅有一只身上带有斑点的奶牛。约翰意识到他的牛群中有一些斑点奶牛，但他从来没有统计过它们的数量。 根据照片，请你帮约翰估算在他的牛群中最多可能有多少只斑点奶牛。如果无解，输出 “-1”。
定义 表示 的牛中带斑点的牛的数量。
三个条件解决问题。于是你要问了，这道题也是妥妥的差分约束啊 emm 为什么要再放一道题呢？
这里我们引入，梦想 SPFA！好好看代码！体会梦想 SPFA 的精髓！（大雾）
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=2e5+5;
int n,m;
struct qxx{int nex,t,v;};
qxx e[N*4];
int h[N],cnt;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}
deque<int> q;
int d[N],tot,cn[N];
bool vis[N];
int spfa(int st){
memset(d,0x3f,sizeof(d));
d[st]=0,q.push_back(st);
while(!q.empty()){
int u=q.front();q.pop_front();
vis[u]=0;
for(int i=h[u];i;i=e[i].nex){
const int &v=e[i].t,&w=e[i].v;
if(d[v]>d[u]+w){
d[v]=d[u]+w,cn[v]=cn[u]+1;
if(!vis[v]){
if(++tot>1926817)return -1;// 那就是梦想！
vis[v]=1;
if(cn[v]>n)return -1;
if(q.size()&&d[v]>d[q.front()])q.push_back(v);
else q.push_front(v);
}
}
}
}
return d[n];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
add_path(a-1,b,1),add_path(b,a-1,-1);
}
for(int i=1;i<=n;i++){
add_path(i-1,i,1),add_path(i,i-1,0);
}
printf("%d",spfa(0));
return 0;
}
最短路图
对于每个结点，将到达这个结点的最短路（可能有多个）上的边做为边集的图称为最短路图（也叫最短路生成图），这里不考虑含有负环的图的最短路图。最短路图是一个 DAG（对于无向图的最短路，我们也只取从源点出发所经过的那条边），这意味着我们可以在最短路图上做拓扑。
[SDOI2009]Elaxia 的路线
求无向图两个点对之间最短路的最长公共路径
最短路边和点的判定
对于以 为源点的最短路，假设所求的 到 的最短路为 .
对于以 为源点的最短路，假设所求的 到 的最短路为 .
则在无向图中
是从 a 到 b 最短路上的点，当且仅当 .
是从 a 到 b 上最短路上的边，当且仅当 .
对于边的判定，这其实是有向的（即 a 到 x 的无向距离 b 到 y 的无向距离）
也就是说， 不一定等于
利用这一点，可以进行拓扑等操作；有时对于两条起点终点相反的边，需要正反两次拓扑。算法如下：
对那四个点分别跑最短路
对于每条边，检验是否是两个最短路图的公共边，并加入到拓扑图中。注意，这里要分同向建边和反向建边。因为原图是无向的，意味着方向相反的两条路径也是合法的。因此要建两次拓扑图。
拓扑排序即可
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define mk make_pair
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
const int N=1503,M=1000000;
int n,m,x1,y1,x2,y2,ans;
int dx1[N],dx2[N],dy1[N],dy2[N];
struct qxx{int nex,t,v;};
qxx e[M];
int h[N],ce;
void add_path(int f,int t,int v){e[++ce]=(qxx){h[f],t,v},h[f]=ce;}
priority_queue<pii,vector<pii>,greater<pii> > q;
void dijkstra(int st,int * d){// 最短路模板
d[st]=0,q.push(mk(0,st));
while(!q.empty()){
pii u=q.top();q.pop();
if(d[u.se]<u.fi)continue;
for(int i=h[u.se];i;i=e[i].nex){
const int &v=e[i].t,&w=e[i].v;
if(d[v]>d[u.se]+w){
d[v]=d[u.se]+w, q.push(mk(d[v],v));
}
}
}
}
#define check1(a,b,c) (dx1[a]+dy1[b]+c==dx1[y1]&&dx2[a]+dy2[b]+c==dx2[y2])
#define check2(a,b,c) (dx1[a]+dy1[b]+c==dx1[y1]&&dx2[b]+dy2[a]+c==dx2[y2])
qxx te[M];
int ht[N],ct,dg[N],f[N];
void tp_add_path(int f,int idx){// 拓扑图加边
te[++ct]=(qxx){ht[f],e[idx].t,e[idx].v},ht[f]=ct,dg[e[idx].t]++;
}
queue<int> qt;
void topu(){// 拓扑排序
for(int i=1;i<=n;i++)if(!dg[i])qt.push(i);
while(!qt.empty()){
int u=qt.front();qt.pop();
for(int i=ht[u];i;i=te[i].nex){
const int &v=te[i].t,w=te[i].v;
dg[v]--, f[v]=max(f[v],f[u]+w);
if(!dg[v])qt.push(v);
}
}
}
int main(){
scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add_path(u,v,w), add_path(v,u,w);
}
//dijkstra
memset(dx1,0x3f,sizeof(dx1));
memset(dx2,0x3f,sizeof(dx2));
memset(dy1,0x3f,sizeof(dy1));
memset(dy2,0x3f,sizeof(dy2));
dijkstra(x1,dx1);
dijkstra(y1,dy1);
dijkstra(x2,dx2);
dijkstra(y2,dy2);
// 双拓扑
for(int i=1;i<=n;i++)
for(int j=h[i];j;j=e[j].nex)
if(check1(i,e[j].t,e[j].v))tp_add_path(i,j);
topu();// 正序
for(int i=1;i<=n;i++)ans=max(f[i],ans);
memset(ht,0,sizeof(ht));ct=0;
memset(dg,0,sizeof(dg));
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=h[i];j;j=e[j].nex)
if(check2(i,e[j].t,e[j].v))tp_add_path(i,j);
topu();// 反向边
for(int i=1;i<=n;i++)ans=max(ans,f[i]);
printf("%d",ans);
return 0;
}
状态转移与最短路
最短路的实质是 DP，因此对于一类非线性结构状态转移都可以用最短路做。
[LuoguP2761] 软件补丁问题
一个软件有 n 个错误，为该软件发放了 m 个补丁程序。
对于每一个补丁 i，都有 2 个与之相应的错误集合 B1[i] 和 B2[i]，使得仅当软件包含 B1[i] 中的所有错误，而不包含 B2[i] 中的任何错误时，才可以使用补丁 i。补丁 i 将修复软件中的某些错误 F1[i]，而同时加入另一些错误 F2[i]。另外，每个补丁都耗费一定的时间。
找到总耗时最少的软件修复方案。
网络流 24 题中隐藏的 SPFA
以软件错误的二进制状态为结点， 表示有错， 表示修复，则相当于在若干对二进制状态中建立转移关系。那么从 到 跑一遍 SPFA 即可
讲一下位运算判断的部分
包含 B1[i] 的所有错误 将当前结点和 B1[i] 做与运算，结果等于 B1[i].
不包含 B2[i] 的任何错误 将 B2[i] 取反，和当前结点做与运算，结果等于当前结点。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=(1<<20)+1,M=105;
int n,m;
int t[M],b1[M],b2[M],f1[M],f2[M];
char b[M],f[M];
struct qxx{int nex,t,v;};
qxx e[(int)2e6];
int h[N],cnt=1;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}
void make(int u){
for(int i=1;i<=m;i++)if((u&b1[i])==b1[i]&&(u&b2[i])==u)
add_path(u,(u&f1[i])|f2[i],t[i]);
}
int dis[N];
bool vis[N],make_edge[N];
void spfa(){
memset(dis,0x3f,sizeof(dis));
queue<int> q;
int s=(1<<n)-1;
q.push(s),dis[s]=0;
while(q.size()){
int u=q.front();q.pop();
vis[u]=0;
if(!make_edge[u])make_edge[u]=1, make(u);// 建边
for(int i=h[u];i;i=e[i].nex){
const int &v=e[i].t,&w=e[i].v;
if(dis[v]<=dis[u]+w)continue;
dis[v]=dis[u]+w;
if(!vis[v])q.push(v),vis[v]=1;
}
}
}
int main(){scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%s%s",&t[i],b+1,f+1);
for(int j=1;j<=n;j++){
if(b[j]=='0')b1[i]<<=1,b2[i]=b2[i]<<1|1;
else if(b[j]=='+')b1[i]=b1[i]<<1|1,b2[i]=b2[i]<<1|1;
else b1[i]<<=1,b2[i]<<=1;//b1:1 有，b2:0 有
if(f[j]=='0')f1[i]=f1[i]<<1|1,f2[i]<<=1;
else if(f[j]=='-')f1[i]<<=1,f2[i]<<=1;
else f1[i]=f1[i]<<1|1,f2[i]=f2[i]<<1|1;//f1:0 有，f2:1 有 }
}//s:(1<<n)-1,t:0
spfa();
printf("%d",dis[0]==0x3f3f3f3f?0:dis[0]);
return 0;
}
[LG1613] 跑路
一个有向图每条边边权都是 1. 你每次可以跑 。问从 1 到 n 的最少次数。可以走重边。图可能有重边。.
一道挺神仙的倍增题
考虑倍增。毕竟题面就透露出满满的倍增气息。
表示走 从 i 到 j 是否可行。这样 DP 的复杂度是 的。然后我们就可以知道一些点对可以一次跑到。于是再把上述 DP 的结果存到 ， 表示从 i 到 j 的最少次数，初始化为 INF。DP 的结果存好后再跑一遍 Floyd 即可。
总复杂度 .
#include<cstdio>
#include<iostream>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
const int N=51,INF=0x3f3f3f3f;
int n,m;
bool f[N][N][70];
int w[N][N];
int main(){
scanf("%d%d",&n,&m);
FOR(i,1,n){
FOR(j,1,n)w[i][j]=INF;
w[i][i]=0;
}
FOR(i,1,m){
int u,v;
scanf("%d%d",&u,&v);
f[u][v][0]=1,w[u][v]=1;
}
FOR(k,1,63) FOR(i,1,n) FOR(j,1,n) {
FOR(p,1,n)f[i][j][k]|=f[i][p][k-1]&f[p][j][k-1];
if(f[i][j][k])w[i][j]=1;
}
FOR(k,1,n) FOR(i,1,n) FOR(j,1,n) w[i][j]=min(w[i][j],w[i][k]+w[k][j]);
printf("%d\n",w[1][n]);
return 0;
}
/*
* BUG#1:L19 忘了初始化 w
*/
[NOIP2017] 逛公园
有向非负权图，设从 1 到 n 的最短路为 d，问从 1 到 n 长度不超过 d+k 的简单路径数。
.
图论 DP。考虑到 ，结合最短路计数的思想，定义 表示从 走到 ，路径长度为 的方案数。其中 表示 到 的最短路长度。
之所以是从 到 的最短路，是因为不是所有点都能走到 ，这样能规避死胡同的情况。在计算 的时候，以 为起点在反图上跑最短路；在计算 的时候，以 1 为起点 DFS 计算。
最后，考虑判环：在 DFS 计算的过程中，随递归的深入， 越来越靠近 ，因此 是非单增的。而出现 环时，会遇到当前的 已被访问过（因为 没变），所以 DFS 的时候记录每个 是否被访问即可。
总复杂度 .
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#define x first
#define y second
#define mk make_pair
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define pii pair<int,int>
using namespace std;
const int N=100005,M=200005,K=52;
// 快读
char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int rd(){
int res=0;char c=nc();
while(!isdigit(c))c=nc();
while(isdigit(c))res=res*10+c-'0',c=nc();
return res;
}
// 快出
void pd(int x){
char c[20];int cnt=0;
while(x)c[++cnt]=x%10+'0',x/=10;
for(int i=cnt;i>0;i--)putchar(c[i]);
}
int n,m,k,p,t;
int d[N],f[N][K],flag;//f[i,j] 表示到结点 i，走 dist[i]+j 的方案数
bool vis[N],w[N][K];
// 前向星存图
struct qxx{int nex,t,v;};
qxx e1[M],e2[M];
int h1[N],c1,h2[N],c2;
void add_path1(int f,int t,int v){e1[++c1]=(qxx){h1[f],t,v},h1[f]=c1;}
void add_path2(int f,int t,int v){e2[++c2]=(qxx){h2[f],t,v},h2[f]=c2;}
// 初始化
void init(){
c1=c2=flag=0;
FOR(i,0,n)h1[i]=0;
FOR(i,0,n)h2[i]=0;
FOR(i,0,n)d[i]=0x3f3f3f3f;
FOR(i,0,n)vis[i]=0;
FOR(i,0,n)FOR(j,0,k)f[i][j]=0;
FOR(i,0,n)FOR(j,0,k)w[i][j]=0;
}
// 反图跑 dijkstra
priority_queue<pii,vector< pii>,greater<pii> > q;
void dijkstra(){
d[n]=0;
q.push(mk(0,n));
while(!q.empty()){pii u=q.top();q.pop();
if(vis[u.y])continue;
vis[u.y]=1;
for(int i=h2[u.y];i;i=e2[i].nex){const int &v=e2[i].t,&w=e2[i].v;
if(d[v]>d[u.y]+w)d[v]=d[u.y]+w, q.push(mk(d[v],v));
}
}
}
//DFS DP
int fdfs(int u,int c){
if(w[u][c])return flag=1,0;// 出现 0 环
if(f[u][c])return f[u][c];// 已被计算
int s=0;
w[u][c]=1;// 标记
for(int i=h1[u];i;i=e1[i].nex){
const int &v=e1[i].t,&val=e1[i].v;
int t=d[u]+c-val-d[v];// 对于 v 需要多走的单位为 t
if(t<0||t>k)continue;
s=(s+fdfs(v,t))%p;
if(flag)return 0;//0 环
}
if(u==n&&c==0)s=1;
return w[u][c]=0,f[u][c]=s;// 撤销标记并返回 f[u][c]
}
int main(){t=rd();
while(t--){
n=rd(),m=rd(),k=rd(),p=rd();
init();
FOR(i,1,m){
int ai=rd(),bi=rd(),ci=rd();
add_path1(ai,bi,ci);
add_path2(bi,ai,ci);
}
dijkstra();
int ans=0;
FOR(i,0,k){
ans=(ans+fdfs(1,i))%p;
if(flag)break;
}
if(flag)puts("-1");
else pd(ans),putchar('\n');
}
return 0;
}
[LG1948] 电话线 Telephone Lines
小清新的 DP 题
加权无向图，求 1 到 n 的路径中第 k+1 大边权最小的路径，输出这个第 k+1 大边权，.
令 表示到结点 i 的第 j 大边权的最小值，对于边 ，转移式如下：
其中箭头表示 DP 转移。既然是在图上的 DP，顺便套一个最短路加速转移即可，复杂度 .
好像还可以二分做。。。不管了
#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=N*N,INF=0x3f3f3f3f;
int n,p,k;
struct qxx{int nex,t,v;};
qxx e[M*2];
int h[N],cnt;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}
int tr(int x,int y){return x*(k+1)+y;}
void rt(int idx,int &x,int &y){x=idx/(k+1),y=idx%(k+1);}
int f[N][N];//f[i,j] 表示到第 i 个点修 j 次的最小的第 j+1 大
typedef pair<int,int> pis;
priority_queue<pis,vector<pis>,greater<pis> > q;
void go(){
memset(f,0x3f,sizeof(f));
for(int j=0;j<=k;j++)f[1][j]=0,q.push(make_pair(0,tr(1,j)));
while(q.size()){
pis u=q.top();q.pop();
int i,j;
rt(u.second,i,j);
if(f[i][j]<u.first)continue;
for(int x=h[i];x;x=e[x].nex){
const int &v=e[x].t,&w=e[x].v;
if(j<k&&f[v][j+1]>f[i][j]){
f[v][j+1]=f[i][j],q.push(make_pair(f[v][j+1],tr(v,j+1)));
}
if(f[v][j]>max(f[i][j],w)){
f[v][j]=max(f[i][j],w),q.push(make_pair(f[v][j],tr(v,j)));
}
}
}
}
int main(){
scanf("%d%d%d",&n,&p,&k);
for(int i=1;i<=p;i++){
int a,b,l;
scanf("%d%d%d",&a,&b,&l);
add_path(a,b,l),add_path(b,a,l);
}
go();
printf("%d",f[n][k]>=INF?-1:f[n][k]);
}
总结
那么讲了这么多所以最短路的应用有什么特点吗？
结果你发现，最短路 TM 就是 DP 啊
为了最后这一句话我就水了一篇文章
