最短路

Dijkstra算法与Floyd算法参考数据结构与算法第八章笔记。

最短路变式：

【最短路】【分层图】Luogu P4568 飞行路线

【题目大意】给出图\(G\)，\(|E|=m,|V|=n,参数k\)，边\((x_i,y_i,w_i)\)表示\(x_i,y_i\)可互相到达，代价为\(w_i\)，求从起始点\(s\)到终点\(t\)经过路径的最小代价，但允许使路径上不超过\(k\)条边的代价减为0（\(k\)次特权）

建立分层图，记使用\(p\)次特权的图为第\(p\)层图，记原边为\((x_i,y_i,w_i)(1\le i\le m)\)按如下标准建边：

\((x_i+nj,y_i+nj,w_i)(0\le j\le k)，对层内建边\)

\((x_i+nj,y_i+n(j+1),0),(y_i+nj,x_i+n(j+1)(0\le j<k))，对层间建边\)

\(mincost=\min\limits_{0\le x\le k}dis_{t+nx}\)

【二分】【最短路】Luogu P1462 通往奥格瑞玛的道路

给出图\(G\)，\(|E|=m,|V|=n,参数k\)，边\((x_i,y_i,w_i)\)表示\(x_i,y_i\)可互相到达，代价为\(w_i\)，到达每个结点需要收费\(p_i\)，求从结点1到结点\(n\)路径总代价不超过\(b\)的前提下，经过结点收费最大值的最小值。

二分结点收费即可，对于每一次跑最短路，如果\(p_v>mid\)则不可更新此结点，最后检验\(dis[n]\le b\)是否成立来进行边界移动。算法时间复杂度为\(O((n+m)\log n),有二分常系数\log maxlen\)

参考解答 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
const int M=1e6+5,N=1e5+5;
int h[M],dis[N],vis[N],n,m,b,p[N],tot;
struct edge{int v,w,next;}a[M];
struct priority
{
    int w,v;
    bool operator<(const priority &x)const
    {
        return x.w<w;
    }
};
void add(int x,int y,int z)
{
    a[++tot]=(edge){y,z,h[x]};
    h[x]=tot;
}
bool check(int mid)
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++) dis[i]=1e9;
    if(p[1]<=mid) dis[1]=0;
    std::priority_queue<priority> q;
    q.push((priority){0,1}); 
    while(!q.empty())
    {
        priority temp=q.top();q.pop();
        int x=temp.v;
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=h[x];i;i=a[i].next)
        {
            int v=a[i].v;
            if(dis[v]>dis[x]+a[i].w&&p[v]<=mid)
            {
                dis[v]=dis[x]+a[i].w;
                if(!vis[v])
                    q.push((priority){dis[v],v});
            }
        }
    }
    return dis[n]<=b;
}
int main()
{
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++) scanf("%d",&p[i]);
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,w);
    }
    if(!check(1e9)){cout<<"AFK";exit(0);}
    int L=0,R=1e9;
    while(L<R)
    {
        int mid=L+R>>1;
        if(check(mid)) R=mid;
        else L=mid+1;
    }
    cout<<L;
    return 0;
}

【负环】Luogu P3385 负环

【负环】【最短路转换】Luogu P5960 差分约束

【同余最短路】Luogu P3403 跳楼机

有向图\(G,|V|=n,|E|=m\)，边的参数为\((x_i,y_i,w_i)\)表示从\(x_i\)到\(y_i\)需要花费时间\(t_i\)，图可划分为\(p\)种路径，从一种路径转到另一种路径需要额外花费时间\(t\)，求从\(\min T_{s\to t}\)

分裂每个节点为\(v_{i,j}\)表示第\(j\)条路径上的\(结点i\)，依次对单条路径建边，对于同一编号的，相互建边\((v_{i,p},v_{i,q},t)\)

最终结果取\(\min dis_{v_{s,k},1\le k\le p}\)

【最小环】Luogu P6175 无向图的最小环问题

【题目大意】给定无向图\(G\),\(|V|=n,|E|=m\)，\(e(x_i,y_i,w_i)\in E\)，表示从\(x_i\)到\(y_i\)存在边权为\(w_i\)双向边。求图中一个至少包含三个点的环，环上结点不重复，且环上的边的长度之和最小，求其边权和。

借用Floyd算法的逻辑，在\(k=k_0\)且未开始本轮算法时，已经得到前\((k-1)\)顶点对之间的最短距离，若存在边\((i,k),(j,k)\)，则有环\(k\to i\to j\to k\)，双层循环枚举\(1\le i<j<k\)进行比较即可。这一部分结束后开始本轮Floyd算法的更新。

参考解答 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
int dis[105][105],e[105][105];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j) e[i][j]=dis[i][j]=1e8;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e[u][v]=e[v][u]=min(e[u][v],w);
        dis[u][v]=dis[v][u]=e[u][v];
    }
    int ans=1e8;
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<k;i++)
            for(int j=i+1;j<k;j++)
            {
                ans=min(ans,dis[i][j]+e[j][k]+e[k][i]);
            }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    }
    if(ans==1e8) printf("No solution.");
    else printf("%d",ans);
    return 0;
}