2017-9-10"切题如切菜杯"模拟赛T4 ZZI

题目

---

YYH拿到了父亲给的钱欣喜若狂，把这些钱拿来造了n栋房子。现在他要给这些房子通电。他有两种方法：第一种是在房间里搭核电发电机发电，对于不同的房子，他需要花不同的代价V_i；，第二种是将有电的房子i的电通过电线通到没电的房子j中，这样子他需要花的代价为a_ij。他现在请你帮他算出他最少要花多少钱才能让所有的房子通上电。

输入格式：

第一行为一个整数 n。接下来的n行为 n 个整数v_i，再接下来的n行每行n个数，第i行第j列的数表示a_ij。

输出格式：

一个整数，表示最小代价。 

样例输入：

4

5

4

4

3

0 2 2 2

2 0 3 3

2 3 0 4

2 3 4 0

样例输出：

9

题解

---

把用核电发电机发电的房子看作与一个有电的0号房子相连，用最小生成树解决。（看懂了题目，就觉得其实挺水的……）

数据范围很小，直接Kruskal或者Prim都行。

代码

---

#define FileIO(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 305
int n,m=0,f[N];
struct edge{int s,t,w;}e[99999];
int find(int x) {
    return ~f[x]?f[x]=find(f[x]):x;
}
inline bool join(int a,int b) {
    int x=find(a),y=find(b);
    if(x==y) return false;
    f[x]=y;return true;
}
bool cmp(edge a,edge b) {
    return a.w<b.w;
}
int kruskal() {
    int cnt=n,ans=0;
    memset(f,~0,sizeof(f));
    std::sort(e,e+m,cmp);
    for(int i=0;i<m;++i) {
        if(join(e[i].s,e[i].t)) {
            ans+=e[i].w;
            if(!--cnt) return ans;
        }
    }
    return -1;
}
int main() {
    FileIO("zzi");
    int a;
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {
        scanf("%d",&a);
        e[m++]={0,i,a};
    }
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=n;++j) {
            scanf("%d",&a);
            if(i<j) e[m++]={i,j,a};
        }
    }
    printf("%d",kruskal());
    return 0;
}