路线规划

nowcoder 217603

题目大意

给一个无向连通图，问你在经过的边最少的前提下，从1走过所有点，再走回1的最短距离

解题思路

对于求出来的路线中，设从1到最后一个点的路径为干线（如图下图，最后一个点为5，干线为1-2-3-5）
对于干线上的边（如2-3），来回各会走两遍
而对于非干线上的边，在去的时候，要离开干线，再回到干线，共两遍
而回来的时候不用走
所以无论是干线上的边还是非干线上的边，都会走两遍
那么对该图做最小生成树，使得所有点都到过一遍，然后乘2即可

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll n, m, x, y, num, ans, fa[200021];
struct node
{
    ll x, y, l;
}a[2000021];
bool cmp(node a, node b)
{
    return a.l < b.l;
}
ll find(ll x)
{
    return x == fa[x]?x:fa[x] = find(fa[x]);
}
int main()
{
    scanf("%lld%lld", &n, &m);
    for (ll i = 1; i <= m; ++i)
        scanf("%lld%lld%lld", &a[i].x, &a[i].y, &a[i].l);
    sort(a + 1, a + 1 + m, cmp);
    for (ll i = 1; i <= n; ++i)
        fa[i] = i;
    num = 1;
    for (ll i = 1; i <= m; ++i)//最小生成树
    {
        x = find(a[i].x);
        y = find(a[i].y);
        if (x != y)
        {
            num++;
            ans += a[i].l;//记录边权
            fa[x] = y;
            if (num == n) break;//这里要用num记录一下，如果所有点都到过了，就直接退出，以减少时间，不然会T
        }
    }
    printf("%lld", ans * 2);
    return 0;
}