【題解】CH6201走廊潑水節 kruskal

題目連結

描述

【簡化版題意】給定一棵N個節點的樹，要求增加若幹條邊，把這棵樹擴充為完全圖，并滿足圖的唯一最小生成樹仍然是這棵樹。求增加的邊的權值總和最小是多少。

我們一共有N個OIER打算參加這個潑水節，同時很湊巧的是正好有N個水龍頭(至于為什麼，我不解釋)。N個水龍頭之間正好有N-1條小道，并且每個水龍頭都可以經過小道到達其他水龍頭(這是一棵樹，你應該懂的..)。但是OIER門為了迎接中中的挑戰，決定修建一些個道路(至于怎麼修，秘密~),使得每個水龍頭到每個水龍頭之間都有一條直接的道路連接配接(也就是構成一個完全圖呗~)。但是OIER門很懶得，并且記性也不好，他們隻會去走那N-1條小道，并且希望所有水龍頭之間修建的道路，都要大于兩個水龍頭之前連接配接的所有小道(小道當然要是最短的了)。是以神COW們，幫那些OIER們計算一下吧，修建的那些道路總長度最短是多少，畢竟修建道路是要破費的~~

輸入格式

本題為多組資料~

第一行t，表示有t組測試資料

對于每組資料

第一行N，表示水龍頭的個數（當然也是OIER的個數）；

2到N行，每行三個整數X,Y,Z；表示水龍頭X和水龍頭Y有一條長度為Z的小道

輸出格式

對于每組資料，輸出一個整數，表示修建的所有道路總長度的最短值。

樣例輸入

2

3

1 2 2

1 3 3

4

1 2 3

2 3 4

3 4 5

樣例輸出

4

17

資料範圍與約定

每個測試點最多10組測試資料

50% n<=1500;

100% n<=6000

100% z<=100

樣例解釋

第一組資料，在2和3之間修建一條長度為4的道路，是這棵樹變成一個完全圖，且原來的樹依然是這個圖的唯一最小生成樹.

跑一遍kruskal，掃描到邊(u,v,w)時，設u所在集合s[u]，v所在集合s[v]，合并s[u]和s[v]時，為了保證(u,v)一定是連接配接s[u],s[v]的最短的邊，是以對于∀x∈s[u] ，∀y∈s[v] ，讓邊(x,y)邊權為w+1.s[u]和s[v]之間一共會增加s[u]* s[v]-1條邊，答案增加(w+1)*(s[u]*s[v]-1)

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=+;
struct Edge{
    int u,v,w;
    bool operator <(const Edge&rhs)const{
    return w<rhs.w;}
}edge[N<<];
int t,n,s[N],fa[N];//s記錄集合大小 
ll ans;
int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);}
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=;i<=n;i++)fa[i]=i,s[i]=;
        ans=;
        int u,v,w;
        for(int i=;i<n;i++)
            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
        sort(edge+,edge+n);
        for(int i=;i<n;i++)
        {
            u=edge[i].u,v=edge[i].v,w=edge[i].w;
            int fu=findfa(u),fv=findfa(v);
            if(fu!=fv)
            {
                fa[fu]=fv;
                ans+=(ll)(w+)*(s[fu]*s[fv]-);
                s[fv]+=s[fu];
            }
        }
        printf("%lld\n",ans);
    }
    return ;
}
           

總結

類似kruskal的操作