新的开始

https://loj.ac/problem/10066

题目描述

　　在一个点建立发电站的费用为v[i]，连接i，j两个节点的费用为p[i][j]，求最小费用使所有节点通电。

思路

　　这道题的难点就在于处理在某一个建发电站的费用，我们可以考虑建一个“大电厂”——0号节点，0号节点到每个节点的距离即为v[i]，由此在图上做一遍最小生成树即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=330;
struct Edge
{
    int x,y,w;
}a[N*N];
int cnt,fa[N];
void add_edge(int x,int y,int v)
{
    a[++cnt].x=x;a[cnt].y=y;a[cnt].w=v;
}
bool cmp(Edge x,Edge y)
{
    return x.w<y.w;
}
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
    int n;
    scanf("%d",&n);
    cnt=0;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        add_edge(0,i,x);
        add_edge(i,0,x);
        fa[i]=i;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            int x;
            scanf("%d",&x);
            if(i^j)
                add_edge(i,j,x);
        }
    sort(a+1,a+cnt+1,cmp);
//    for(int i=1;i<=cnt;i++)
//        printf("%d\n",a[i].w);
    int s=0,k=0;
    for(int i=1;i<=cnt;i++)
    {
        int fx=find(a[i].x),fy=find(a[i].y);
        if(fx!=fy)
        {
            fa[fx]=fy;
            s+=a[i].w;
            k++;
            if(k==n)break ;
        }
    }
    printf("%d",s);
    return 0;
}