最短路径生成树—介绍

53 阅读 0 评论 35 点赞

我是靠谱客的博主动听向日葵，最近开发中收集的这篇文章主要介绍最短路径生成树—介绍，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

例题

在顺利攻破Lord lsp的防线之后，lqr一行人来到了Lord lsp的城堡下方。Lord lsp黑化之后虽然拥有了强大的超能力，能够用意念力制造建筑物，但是智商水平却没怎么增加。现在lqr已经搞清楚黑暗城堡有N个房间 (1≤N≤1000)，M条可以制造的双向通道，以及每条通道的长度。
lqr深知Lord lsp的想法，为了避免每次都要琢磨两个房间之间的最短路径，Lord lsp一定会把城堡修建成树形的；但是，为了尽量提高自己的移动效率，Lord lsp一定会使得城堡满足下面的条件：设 D[i] 为如果所有的通道都被修建，第 i 号房间与第1号房间的最短路径长度；而 S[i] 为实际修建的树形城堡中第 i 号房间与第1号房间的路径长度；要求对于所有整数 i(1≤i≤N)，有 S[i]=D[i] 成立。
为了打败Lord lsp，lqr想知道有多少种不同的城堡修建方案。于是lqr向applepi提出了这个问题。因为applepi还要忙着出模拟赛，所以这个任务就交给你了。当然，你只需要输出答案对 2^31–1 取模之后的结果就行了。

最短路径生成树介绍

最短路径生成树是一棵树，它的根节点为S，在这棵树上跑dijkstra与在原图上跑得到的d会是完全一样的。
这棵树的生成可以用dijkstra来理解。每个未被标记的节点把d推priority_queue，取出堆顶x，x先被标记。然后更新与x相连的节点，如果有d[y]>d[x]+e[k].c，那么把y节点以及k这条边一起选入预定的最小路径生成树。当y被标记时，这条预定的边变成实际的最小路径生成树的一条边。
再理解一下，dijkstra看似随机的从priority_queue中随机的取点，实际上它取的点还是有原则的。画一个图出来，YY一下，可以发现dijkstra的扩展路径就是一棵树，（很满足树的特性，一个点有很多个孩子节点，每个点只有一个父亲……）把这棵树提取出来便是最小路径生成树啦。

例题解析

最短路径生成树
每个点的d[i]显然是一个固定值，我们可以先跑一遍dijkstra得到每个点的d。
接下来就考虑计数了。
我们把每个点按d[i]递增排序，这么做的目的是让计数有顺序，因为每个距离远的可以从距离近的转移过来，所以要先遍历距离近的点。遍历过的节点加入集合T，未遍历的存在集合S。接下来每次从集合S中拿出一个点，加入集合T，如果它有cnt中方案满足 $d[y]=d[x]+edge(x,y)(xin T,yin S)$ ，将它们累乘即是答案。
因为我们能够保证T集合中的点都是可以用最短距离达到的，我们随意接在一个点的后面，使得新加入的点也具有了s[i]=d[i]的性质。这些方案都可以计入答案。
最后抛出博主的一个问题：排序真的有用吗？我把排序去掉，并把第二个for改成1~n也过了数据。求大神解释~

UPDATE：
好吧，我要当一回“大神”了。
排序是无所谓的，因为我们要找的是哪一个d[j]满足d[j]=d[i]+ma[i][j]（这题可能有多个j满足此条件）。如果排序了的话，那么答案就一定在1~i-1，否则答案就可能在1~n任意位置，所以j要枚举1~n。时间估计差不多吧，看你喜欢打喽。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll mod=(1ll<<31)-1;
const int maxn=1010,maxm=500000;

int n,m;

struct E{int y,c,next;}e[maxm*2];int len=0,last[maxn];
void ins(int x,int y,int c)
{
    e[++len]=(E){y,c,last[x]};last[x]=len;
}

int d[maxn];bool v[maxn];
priority_queue<pii,vector<pii>,greater<pii> > q;
void dijkstra()
{
    memset(d,63,sizeof(d));d[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int x=q.top().second;q.pop();//debug pop
        if(v[x]) continue;
        v[x]=true;
        for(int k=last[x];k;k=e[k].next)
        {
            int y=e[k].y;
            if(d[y]>d[x]+e[k].c)
            {
                d[y]=d[x]+e[k].c;
                q.push(make_pair(d[y],y));
            }
        }
    }
}

int id[maxn];
bool cmp(int i1,int i2)
{
    return d[i1]<d[i2];
}

int ma[maxn][maxn];
int main()
{
    memset(ma,63,sizeof(ma));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        ma[x][y]=ma[y][x]=c;
        ins(x,y,c);ins(y,x,c);
    }
    
    dijkstra();
    
    for(int i=1;i<=n;i++) id[i]=i;
    sort(id+1,id+n+1,cmp);
    ll ans=1,cnt;
    for(int i=2;i<=n;i++)//debug ans=0乘法初始化为1 
    {
        cnt=0;
        for(int j=i-1;j>=1;j--)
        {
            if(d[id[i]]==d[id[j]]+ma[id[i]][id[j]]) cnt++;//debug 反了 
        }
        ans=ans*cnt%mod;
    }
    printf("%lldn",ans);
    return 0;
}