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

题目

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

输入格式：

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

输出格式：

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

样例输入：

0 2 2 2

2 0 3 3

2 3 0 4

2 3 4 0

样例输出：

题解

把用核电发电机发电的房子看作与一个有电的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=,f[N];

 struct edge{int s,t,w;}e[];

 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=;

     memset(f,~,sizeof(f));

     std::sort(e,e+m,cmp);

     for(int i=;i<m;++i) {

         if(join(e[i].s,e[i].t)) {

             ans+=e[i].w;

             if(!--cnt) return ans;

         }

     }

     return -;

 }

 int main() {

     FileIO("zzi");

     int a;

     scanf("%d",&n);

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

         scanf("%d",&a);

         e[m++]={,i,a};

     }

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

         for(int j=;j<=n;++j) {

             scanf("%d",&a);

             if(i<j) e[m++]={i,j,a};

         }

     }

     printf("%d",kruskal());

     return ;

 }

Code

巴特西

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

最新文章

热门文章