前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >51Nod-1443-路径和树

51Nod-1443-路径和树

作者头像
f_zyj
发布2018-01-09 10:55:16
5200
发布2018-01-09 10:55:16
举报
文章被收录于专栏:ACM小冰成长之路

ACM模版

描述

描述
描述

题解

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

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

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

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

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

代码

代码语言:javascript
复制
#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;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年09月24日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 描述
  • 题解
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档