图上的严格次路径 – Zechel

狄杰特斯拉定理不仅可以用来求最短路,同时也可以在同样的复杂度里完成次短路的计算。

核心在于开两个数组,分别记录最短路和次短路,当一个点转移到另一个点时,可以通过比较其值和当前点的最短路和次短路值的大小,来进行更新。

另外的功能是,可以统计有起点和终点之间,存在多少条最短路径,以及多少条此短路径。

模板代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1005,H=10005,INF=0x3f3f3f3f;
typedef pair<int,int> P;
int N,M;
int Head[maxn],Next[H],ver[H],edge[H],tot=0;
inline void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z;
    Next[tot]=Head[x];
    Head[x]=tot;
}
priority_queue<P,vector<P>,greater<P> >Q;
int d[3][maxn],sum[3][maxn];
void pre(int sit)
{
    fill(d[0],d[0]+maxn,INF);
    fill(d[1],d[1]+maxn,INF);
    memset(sum,0,sizeof(sum));
    d[0][sit]=0;
    sum[0][sit]=1;
    Q.push(make_pair(0,sit));
    while(!Q.empty())
    {
        P tmp=Q.top();
        Q.pop();
        int x=tmp.second,v=tmp.first;
        int k=-1;
        if(d[0][x]==v)k=0;
        if(d[1][x]==v)k=1;
        if(k==-1)continue;
        for(int i=Head[x];i;i=Next[i])
        {
            int y=ver[i],z=edge[i];
            if(d[0][y]>v+z)
            {
                d[1][y]=d[0][y];
                sum[1][y]=sum[0][y];
                d[0][y]=v+z;
                sum[0][y]=sum[k][x];
//由于在上一次最短路被更新时,已经被push过一次了,所以不需要再push一次刚刚更新的次短路,避免重复
                Q.push(make_pair(d[0][y],y));
            }
            else if(d[0][y]==v+z)
            {
                sum[0][y]+=sum[k][x];
            }
            else if(d[1][y]>v+z)
            {
                d[1][y]=v+z;
                sum[1][y]=sum[k][x];
                Q.push(make_pair(d[1][y],y));
            }
            else if(d[1][y]==v+z)
            {
                sum[1][y]+=sum[k][x];
            }
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        tot=0;
        memset(Head,0,sizeof(Head));
        memset(Next,0,sizeof(Next));
        scanf("%d %d",&N,&M);
        int a,b,c;
        for(int i=1;i<=M;i++)
        {
            scanf("%d %d %d",&a,&b,&c);
            add(a,b,c);
        }
        int S,F;
        scanf("%d %d",&S,&F);
        pre(S);
        int ans=sum[0][F];
        if(d[0][F]+1==d[1][F])ans+=sum[1][F];
        printf("%d\n",ans);
    }
}

如果只是求最短路和此短路,我们可以用贪心优化,将上述代码进行优化,可以更快的得到答案。

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    } 
    while('0' <= ch && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    } return x * f;
}
const int maxn=5005,H=100005,INF=0x3f3f3f3f;
struct imf{
    int x,y,type;
    bool operator < (const imf &W) const{
        return x > W.x;
    }
};
int N,M;
int Head[maxn],Next[2*H],ver[2*H],edge[2*H],tot=0;
inline void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z;
    Next[tot]=Head[x];
    Head[x]=tot;
}
bool vis[maxn][3];
priority_queue<imf>Q;
int d[3][maxn];
void pre(int sit)
{
    fill(d[0],d[0]+maxn,INF);
    fill(d[1],d[1]+maxn,INF);
    d[0][sit]=0;
    Q.push((imf){0,1,0});
    while(!Q.empty())
    {
        imf tmp=Q.top();
        Q.pop();
        int x=tmp.y,v=tmp.x;
        if(vis[x][tmp.type])continue;
        vis[x][tmp.type]=true;
        for(int i=Head[x];i;i=Next[i])
        {
            int y=ver[i],z=edge[i];
            if(d[0][y]>v+z)
            {
                d[1][y]=d[0][y];
                d[0][y]=v+z;
                Q.push((imf){d[0][y],y,0});
                Q.push((imf){d[1][y],y,1});
            }
            else if(d[1][y]>v+z&&v+z>d[0][y])
            {
                d[1][y]=v+z;
                Q.push((imf){d[1][y],y,1});
            }
        }
    }
}
int main()
{
    scanf("%d %d",&N,&M);
    int a,b,c;
    for(int i=1;i<=M;i++)
    {
        a=read(),b=read(),c=read();
        add(a,b,c);
        add(b,a,c);
    }
    pre(1);
    printf("%d",d[1][N]);
}

注意到两段代码有所不同,其主要原因是,前者需要求路径,所以必须保证不重不漏,那么就不能利用贪心快速求解,主体上差别不大,第一段代码虽然速度略慢,但功能相对更强。

再附加次小生成树的模板代码,主要用到了树上倍增的思想

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long ll;
struct edge
{
    int x,y,z;
}T[3*maxn];
int N,M;
int f[maxn],Head[maxn],ver[2*maxn],Next[2*maxn],Edge[2*maxn],tot=0,t,fa[maxn][20],d[maxn],G[maxn][20][3],re[3*maxn];
int td[maxn],cnt=0;
queue<int>Q;
void add(int x,int y,int z)
{
    ver[++tot]=y,Edge[tot]=z;
    Next[tot]=Head[x];
    Head[x]=tot;
}
int get(int x)
{
    if(x==f[x])return x;
    return f[x]=get(f[x]);
}
int cmp(edge a,edge b)
{
    return a.z<b.z;
}
void dsf()
{
    d[1]=1,Q.push(1);
    while(!Q.empty())
    {
        int x=Q.front();
        Q.pop();
        for(int i=Head[x];i;i=Next[i])
        {
            int y=ver[i];
            if(d[y])continue;
            d[y]=d[x]+1;
            fa[y][0]=x;
            G[y][0][0]=Edge[i];
            G[y][0][1]=-1000000000;
            for(int j=1;j<=t;j++)
            {
                fa[y][j]=fa[fa[y][j-1]][j-1];
                G[y][j][0]=max(G[y][j-1][0],G[fa[y][j-1]][j-1][0]);
                if(G[y][j-1][0]==G[fa[y][j-1]][j-1][0])
                {
                    G[y][j][1]=max(G[y][j-1][1],G[fa[y][j-1]][j-1][1]);
                }
                else if(G[y][j-1][0]<G[fa[y][j-1]][j-1][0])
                {
                    G[y][j][1]=max(G[y][j-1][0],G[fa[y][j-1]][j-1][1]);
                }
                else if(G[y][j-1][0]>G[fa[y][j-1]][j-1][0])
                {
                    G[y][j][1]=max(G[y][j-1][1],G[fa[y][j-1]][j-1][0]);
                }
            }
            Q.push(y);
        }
    }
}
int solve(int x,int y,int z)
{
    if(d[x]>d[y])swap(x,y);
    int s1=-1000000000,s2=-1000000000;
    cnt=0;
    for(int i=t;i>=0;i--)
    {
        if(d[fa[y][i]]>=d[x])
        {
            td[++cnt] = G[y][i][0];
            td[++cnt] = G[y][i][1]; 
            y = fa[y][i];
        }
    }
    if(x!=y)
    {
        for(int i=t;i>=0;i--)
        {
            if(fa[x][i]!=fa[y][i])
            {
                td[++cnt] = G[x][i][0];
                td[++cnt] = G[x][i][1];
                td[++cnt] = G[y][i][0];
                td[++cnt] = G[y][i][1];
                x=fa[x][i],y=fa[y][i];
            }
        }
        td[++cnt] = G[x][0][0]; td[++cnt] = G[x][0][1]; 
        td[++cnt] = G[y][0][0]; td[++cnt] = G[y][0][1]; 
    }
     for (int i = 1; i <= cnt; i++) {
        if (td[i] > s1) {
            s2 = s1; s1 = td[i];
        } else if (td[i] != s1 && td[i] > s2) s2 = td[i];
    } 
    if (z > s1) return s1;
    return s2;
}
int main()
{
    scanf("%d %d",&N,&M);
    for(int i=1;i<=M;i++)scanf("%d %d %d",&T[i].x,&T[i].y,&T[i].z);
    sort(T+1,T+M+1,cmp);
    for(int i=1;i<=N;i++)f[i]=i;
    ll sum=0;
    for(int i=1;i<=M;i++)
    {
        int x=get(T[i].x),y=get(T[i].y);
        if(x==y)continue;
        f[x]=y;
        re[i]=1;
        sum+=T[i].z;
        add(T[i].x,T[i].y,T[i].z);
        add(T[i].y,T[i].x,T[i].z);
    }
    t=(int)(log(N)/log(2))+1;
    dsf();
    ll ans=100000000000000000;
    for(int i=1;i<=M;i++)
    {
        if(re[i])continue;
        ans=min(ans,sum+T[i].z-solve(T[i].x,T[i].y,T[i].z));
    }
    printf("%lld",ans);
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

川公网安备 51130202000337号