专栏首页ACM小冰成长之路51Nod-1443-路径和树

51Nod-1443-路径和树

ACM模版

描述

题解

这个题是单源最短路 + 最小生成树。

首先我们来介绍一下题中所述的最短路径树是什么,我们都知道,给定一个 uu 求单源最短路时,所有的最短路路径通常能够恰好构成一棵树,那么这棵树就是最短路径树。

可是我们这里为什么还要用最小生成树呢?这很容易理解,前文我提到,通常可以构成一棵树,那就自然有不通常的情况,如果从 u 到达一个结点 v 的最短路径不唯一呢?所以我们应该获取所有的最短路径边,从这些边中进行最小生成树,当然,这里有一个优化,当这些边数刚好等于结点数减一时,就不用生成树了。

这时我们考虑,我们如何获取最短路径呢?自然是通过单源最短路中的 dist[] 来获取,这里大概不能直接在求单源最短路时存储最短路径,因为那样就无法获取所有的最短路径了。

约莫就是这些,其实有一点我无法确定并且证明,就是如果对于这种不通常的情况,是否是取任何一条最短路都合法呢?如果是这样,那么最小生成树部分不就可以省去了吗?

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

typedef long long ll;

const int MAXN = 3e5 + 10;

int n, m;
int vis[MAXN];
int pre[MAXN];
int bz[MAXN];
ll dist[MAXN];

vector<pair<int, ll> > vpil[MAXN];
queue<int> qi;

struct Edge
{
    int u, v;
    ll cost;
    Edge(int U = -1, int V = -1, ll C = -1)
    {
        u = U;
        v = V;
        cost = C;
    }

    bool operator < (const Edge &x) const
    {
        return cost < x.cost;
    }
};

vector <Edge> edge;

int find(int x)
{
    if (x == pre[x])
    {
        return x;
    }
    else
    {
        return pre[x] = find(pre[x]);
    }
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
    {
        return ;
    }
    pre[x] = pre[y];
}

void spfa(int star)
{
    memset(dist, -1, sizeof(dist));
    memset(vis, 0, sizeof(vis));

    while (!qi.empty())
    {
        qi.pop();
    }
    dist[star] = 0;
    vis[star] = 1;
    qi.push(star);
    while (!qi.empty())
    {
        int now = qi.front();
        qi.pop();
        vis[now] = 0;
        int sz = (int)vpil[now].size();
        for (int i = 0; i < sz; i++)
        {
            int v = vpil[now][i].first;
            ll cost = vpil[now][i].second;
            if (dist[v] == -1 || dist[v] > dist[now] + cost)
            {
                dist[v] = dist[now] + cost;
                if (!vis[v])
                {
                    vis[v] = 1;
                    qi.push(v);
                }
            }
        }
    }
}

ll Kruskal()
{
    ll ret = 0;
    memset(bz, 0, sizeof(bz));
    sort(edge.begin(), edge.end());

    int sz = (int)edge.size();
    for (int i = 0; i < sz; i++)
    {
        int u = edge[i].u, v = edge[i].v;
        ll cost = edge[i].cost;
        if (bz[v] || find(u) == find(v))
        {
            continue;
        }
        bz[v] = 1;
        merge(u, v);
        ret += cost;
    }

    return ret;
}

int main()
{
    while (scanf("%d%d", &n, &m) != EOF)
    {
        for (int i = 0; i <= n; i++)
        {
            vpil[i].clear();
            pre[i] = i;
        }

        int u, v, cost;
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d%d", &u, &v, &cost);
            vpil[u].push_back(make_pair(v, (ll)cost));
            vpil[v].push_back(make_pair(u, (ll)cost));
        }

        int star;
        scanf("%d", &star);

        spfa(star);
        edge.clear();

        for (int i = 1; i <= n; i++)
        {
            int sz = (int)vpil[i].size();
            for (int j = 0; j < sz; j++)
            {

                int v = vpil[i][j].first;
                ll cost = vpil[i][j].second;
                if (dist[v] == dist[i] + cost)
                {
                    edge.push_back(Edge(i, v, cost));
                }
            }
        }

        printf("%lld\n", Kruskal());
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ZOJ-3329-One Person Game

    ACM模版 描述 ? ? 题解 kuangbin 大佬的题解,神乎其技: ? 代码 #include <iostream> #include <cstdio> ...

    f_zyj
  • HDU-5575-Discover Water Tank

    ACM模版 描述 ? 题解 左偏树可解。 初始默认所有 z=0z = 0 的情况,然后枚举 z=1z = 1 的情况来更新答案,并且可以用并查集来维护合并的水箱...

    f_zyj
  • 51Nod-1203-JZPLCM

    ACM模版 描述 ? 题解 这个题的解法好像好多好多,可以线段树解,自然也可以用树状数组解,还有大佬直接莫队推过,我这里用的树状数组搞得。 首先将数进行拆解,拆...

    f_zyj
  • 搜索(4)

    mathor
  • Contest 176 - LeetCode 1353. Maximum Number of Events That Can Be Attended (贪心)

    题意:有n个节目,每个节目有一个持续的天数,你一天只能看一个节目,问你这么多天最多能看几个节目

    ShenduCC
  • HDU 5677 ztr loves substring(回文串加多重背包)

    ztr loves substring Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 655...

    ShenduCC
  • Java经典编程50题(面试笔试机试)

    https://blog.csdn.net/alias_fa/article/details/52985112

    林万程
  • 1001 舒适的路线 2006年

    1001 舒适的路线 2006年 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Descrip...

    attack
  • 剑指offer 和为s的两个数字

    输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

    week
  • P1967 货车运输 未完成

    1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<c...

    attack

扫码关注云+社区

领取腾讯云代金券