灌水

Farmer John已经决定把水灌到他的n(1≤n≤300)块农田，农田被数字1到n标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。 建造一个水库需要花费wi(1≤wi≤105),连接两块土地需要花费pij。 计算Farmer John所需的最少代价。
输入描述:

第一行：一个数n。

第二行到第n+1行：第i+1行含有一个数wi。

第n+2行到第2∗n+1行：第n+1+i行有n个被空格分开的数，第j个数代表pij。

输出描述:

一个单独的数代表最小代价.

示例1
输入

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

输出

9

guanshui.cppview raw

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 310;
int fa[N];

struct Edge{
    int a, b, v;
}edges[N*N];

int n;
int tot;
int find(int x){
    if(x==fa[x]) return x;
    return fa[x] = find(fa[x]);
}

bool cmp(Edge &a, Edge&b){
    return a.v < b.v;
}

int main(){
    scanf("%d", &n);
    int val;

    for(int i=1;i<=n;i++){
        scanf("%d", &val);
        edges[++tot].a = 0, edges[tot].b = i, edges[tot].v = val;
    }

    for(int i=1;i<n;i++)
        for(int j=1;j<=n;j++){
            scanf("%d", &val);
            if(i<j)
                edges[++tot].a= i, edges[tot].b = j, edges[tot].v = val;
        }


    for(int i=0;i<=n;i++) fa[i] = i;
    int ans = 0;
    sort(edges+1, edges+tot+1, cmp);
    for(int i=1;i<=tot;i++){
        int a = find(edges[i].a);
        int b = find(edges[i].b);
        if(a!=b) fa[a] = b, ans += edges[i].v;
    }

    printf("%d\n", ans);
    return 0;

}