安慰奶牛Cheering up the Cow

一次a就很开心

可以当作kruskal模板题（orz

--------------------------------------------------------------------------------------

约翰有N个牧场，编号依次为1到N。每个牧场里住着一头奶牛。连接这些牧场的有P条道路，每条道路都是双向的。第j条道路连接的是牧场Sj和Ej，通行需要Lj的时间。两牧场之间最多只有一条道路。约翰打算在保持各牧场连通的情况下去掉尽量多的道路。

约翰知道，在道路被强拆后，奶牛会非常伤心，所以他计划拆除道路之后就去忽悠她们。约翰可以选择从任意一个牧场出发开始他维稳工作。当他走访完所有的奶牛之后，还要回到他的出发地。每次路过牧场i的时候，他必须花Ci的时间和奶牛交谈，即使之前已经做过工作了，也要留下来再谈一次。注意约翰在出发和回去的时候，都要和出发地的奶牛谈一次话。请你计算一下，约翰要拆除哪些道路，才能让忽悠奶牛的时间变得最少？

--------------------------------------------------------------------------------------

新的边权为原边权*2+边的两端点的点权值

Kruskal一边

再加上最小的点权（把它当作起点

O(mlogm)

--------------------------------------------------------------------------------------

#include<cstdio>

#include<algorithm>

#include<iostream>

using namespace std;

inline int read()

{

    int sum = ,p = ;

    char ch = getchar();

    while(ch < '' || ch > '')

    {

        if(ch == '-')

            p = -;

        ch = getchar();

    }

    while(ch >= '' && ch <= '')

    {

        (sum *= ) += ch - '';

        ch = getchar();

    }

    return sum * p;

}

int n,p,ans;

int val[];

int head[],cnt;

struct edge

{

    int to,wei,frm;

}e[];

int fa[];

bool cmp(edge a,edge b)

{

    return a.wei < b.wei;

}

int findfa(int o)

{

    if(fa[o] == o)

        return o;

    else

        return fa[o] = findfa(fa[o]);

}

void kruskal()

{

    int k = ;

    for(int i = ;i <= n;i++)

        fa[i] = i;

    sort(e+,e+p+,cmp);

    for(int i = ;i <= p;i++)

    {

        int a = findfa(e[i].frm);

        int b = findfa(e[i].to);

        if(a == b)

            continue;

        ans += e[i].wei;

        fa[a] = b;

        if(++k == n - )

            break;

    }

}

int main()

{

    n = read(),p = read();

    for(int i = ;i <= n;i++)

        val[i] = read();

    for(int i = ;i <= p;i++)

    {

        int a= read(),b = read(),c = read();

        e[++cnt].frm = a;

        e[cnt].to = b;

        e[cnt].wei = val[a] + val[b] + c * ;

    }

    kruskal();

    sort(val+,val++n);

    printf("%d",ans + val[]);

    return ;

}

巴特西

安慰奶牛Cheering up the Cow

最新文章

热门文章