超超超冷门的算法之最短路径生成树（SPT）

· · 算法·理论

什么是最短路径生成树？

画图：

假设我们的源点是 C，那么，最短路径生成树就是以 C 为源点的到达每个点的路径最短的生成树（简单无向带权连同图）。

我们直接按照贪心思路求出一个最短路径生成树（按照优先选边权小的，就是 \texttt{Dijkstra} 的贪心思路）。

可以发现，选出来的路径是：C \to E \to B \to A。如果用 dis_i 表示从原点走到某个点的距离，则：

dis_C = 0\\ dis_E = 6\\ dis_B = 8\\ dis_A = 8

如果把走到的边都选中，那么选中的边就是一个最短路径生成树了。

但是，这张图不止这样的路径，还有许多的路径也可以达到同样的效果，例如：C \to A \to B，然后C \to E，或者 C \to E \to B，然后C \to A。如果在更加复杂的图里面，甚至会更多，所以，我们要根据题目的要求来求。

我们先来看第一道题。

CF545E Paths and Trees

思路

这题一看，和最短路径生成树很像，但是要求权值总和最小，我们再来观察上图：

C \to E \to B \to A 的权值总和：8。

C \to A \to B，然后C \to E 的权值总和：14。

C \to E \to B，然后C \to A 的权值总和：16。

C \to A \to B \to E 的权值总和：10。

不同的最短路径生成树的权值总和是不一样的。

然后，题目还说要输出边的编号。

那么，我们在储存边的时候，要多使用一个 id 存编号。既然要输出路径，就可以记录这个点是从哪里来的就行了，然后使用 val_i 表示第 i 条边的边权，最后加上边权。

在判断成功的时候，我们记录 pre_v \gets new_{id}，因为新的点足够优秀，可以更新前面的点。

当然，我们还要判断是不是等于，因为如果路径等于，权值不一定等于，上方的图已经说明了这点。

那么，如果等于，并且权值更优的话，则也要记录，但是不要重复加入队列当中，因为队列记录的是路径，而不是权值总和。这样只会让爆空间的可能新更大。

如果将所有的点都更新了，则直接循环每一个点，只要不是起点，就加上 pre_i 的权值，然后把编号丢进向量里面，最后排个序输出就行了。

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5,inf=1e18;
int n,m,s,dis[N],pre[N],val[N];
bool vis[N];
struct edge{
    int v,w,id;
};
vector<edge> g[N];
struct no{
    int id,w;
    bool operator <(const no& rhs) const
    {
        return w>rhs.w;
    }
};
void dijkstra()
{
    for(int i=1;i<=n;++i)
    {
        dis[i]=inf;
        vis[i]=0;
    }
    priority_queue<no> q;
    q.push({s,0});
    dis[s]=0;
    while(!q.empty())
    {
        int u=q.top().id;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto V:g[u])
        {
            int v=V.v;
            if(vis[v]==0&&dis[v]>dis[u]+V.w)
            {
                dis[v]=dis[u]+V.w;
                pre[v]=V.id;
                q.push({v,dis[v]});
            }
            if(vis[v]==0&&dis[v]==dis[u]+V.w&&V.w<val[pre[v]])
            {
                pre[v]=V.id;
            }
        }
    }
    return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back({y,z,i});
        g[y].push_back({x,z,i});
        val[i]=z;
    }
    cin>>s;
    dijkstra();
    int sum=0;
    vector<int> ans;
    for(int i=1;i<=n;++i)
    {
        if(i==s) continue;
        sum+=val[pre[i]];
        ans.push_back(pre[i]);
    }
    sort(ans.begin(),ans.end());
    cout<<sum<<'\n';
    for(auto it:ans) cout<<it<<' ';
    return 0;
}

CF1076D Edge Deletion

思路

洛谷翻译有误，因为第一句话的说明指的是一棵树，但是这是我们最终的目的，而且 n - 1 \le m。

我们还是画一个图理解（第一问）。

假设此时 n = 5 , k = 3。

不难发现，这个图至多有 k 个好点。因为源点也算一个。

但是，如果 k > n 怎么办？只有 n 个点，不够 k，所以最终的答案很简单是 \min(k , n - 1)。

接下来就是第二问了。

如果 pre_i = id，是不是就说明它没有被其它的点更新过？肯定是的，如果没有被更新，说明它就是一个好点。所以，我们可以使用 DFS 来做，就是直接往下走，看下一个点是不是 pre_v = id，如果是，说明可以输出，然后输出的个数加一，如果超过了 k，就停止。

还需要注意如果 k 是 0，输出完 \min(k , n - 1) 之后就什么也不干。

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5,inf=1e18;
int n,m,k,dis[N],pre[N],val[N];
bool vis[N];
struct edge{
    int v,w,id;
};
vector<edge> g[N];
struct no{
    int id,w;
    bool operator <(const no& rhs) const
    {
        return w>rhs.w;
    }
};
void dijkstra()
{
    for(int i=1;i<=n;++i)
    {
        dis[i]=inf;
        vis[i]=0;
    }
    priority_queue<no> q;
    q.push({1,0});
    dis[1]=0;
    while(!q.empty())
    {
        int u=q.top().id;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto V:g[u])
        {
            int v=V.v;
            if(vis[v]==0&&dis[v]>dis[u]+V.w)
            {
                dis[v]=dis[u]+V.w;
                pre[v]=V.id;
                q.push({v,dis[v]});
            }
            if(vis[v]==0&&dis[v]==dis[u]+V.w&&V.w<val[pre[v]])
            {
                pre[v]=V.id;
            }
        }
    }
    return;
}
int cnt;
void dfs(int u,int fa)
{
    for(auto V:g[u])
    {
        int v=V.v;
        if(pre[v]==V.id&&v!=fa)
        {
            cnt++;
            if(cnt>k) exit(0);
            cout<<V.id<<' ';
            dfs(v,u);
        }
    }
    return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=m;++i)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back({y,z,i});
        g[y].push_back({x,z,i});
        val[i]=z;
    }
    dijkstra();
    cout<<min(k,n-1)<<'\n';
    if(k) dfs(1,0);
    return 0;
}

\texttt{The End.}