最短路应用

摘要

本文接上文 最短路算法,为大家介绍最短路的常见应用。

将原来打的各种题目的零散文章汇总,编入精选文章。

负环与差分约束

一个看起来不像最短路的最短路应用。给出一组差分约束,问是否有解。差分约束是形容 的式子。可以将这样的式子转化为 的形式。这就像一个松弛操作的式子。我们的目标是找到合适的 使得 ,若 分别表示一个图中的最短路长度,那么这个式子的含义就是 无法从 松弛!

因此可以把 转化为 的形式,表示结点 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 的无向距离)

也就是说, 不一定等于

利用这一点,可以进行拓扑等操作;有时对于两条起点终点相反的边,需要正反两次拓扑。算法如下:

  1. 对那四个点分别跑最短路

  2. 对于每条边,检验是否是两个最短路图的公共边,并加入到拓扑图中。注意,这里要分同向建边和反向建边。因为原图是无向的,意味着方向相反的两条路径也是合法的。因此要建两次拓扑图。

  3. 拓扑排序即可

#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 即可

讲一下位运算判断的部分

  1. 包含 B1[i] 的所有错误 将当前结点和 B1[i] 做与运算,结果等于 B1[i].

  2. 不包含 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 啊

为了最后这一句话我就水了一篇文章


  转载请注明: Sshwy's Blog 最短路应用

 上一篇
从树套树浅析常用结构的特性 从树套树浅析常用结构的特性
摘要 2019.6.18 编入精选文章 作者严正声名:本文比较沙雕。 另外,本文并不是 “树套树入门” 的文章,而是一篇议论性文章。议论性文章是指可能内容较受争议。 在我写这文章的时侯,输入法:蜀涛数,树桃树,树套数…… emm 就是没有树
2019.06.17
下一篇 
博客转型计划 博客转型计划
摘要 再小的星星也有光芒 没错!你现在看到的是 Sshwy 大菜鸡的一个计划! 心的起始每个人都是有故事的,也是有追求的。在 OI 这条路上,学习知识的时侯大多数人估计直接奔 OIWIKI 了,包括我。那么,为什么我要写这个博客?并不是单
2019.06.14
  目录