zoj 1586

裸kruskal。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define MAX 1010
#define INF 0x3f3f3f3f

using namespace std;
int n;
int link[MAX];
int map[MAX][MAX];

struct E {
 int s, e, len;

} edge[1000010];
bool cmp(const E &a, const E &b) { return a.len < b.len; }
int nume;
int Father[MAX];
int find(int x) {
 if (x != Father[x])
   return find(Father[x]);
 else
   return x;
}

bool Union(int a, int b) {
 int fax = find(a);
 int fay = find(b);
 if (fax == fay)
   return false;
 else {
   Father[fax] = fay;
   return true;
 }
}

int kruskal() {
 int cnt = 0;
 int sum = 0;
 sort(edge, edge + nume, cmp);
 for (int i = 0; i < n; i++) {
   Father[i] = i;
 }

 for (int i = 0; i < nume; i++) {
   if (Union(edge[i].s, edge[i].e)) {
     sum += edge[i].len;
     cnt++;
   }
 }

 return sum;
}

int main(int argc, char const *argv[]) {
 int t;
 scanf("%d", &t);
 while (t--) {
   nume = 0;
   scanf("%d", &n);
   for (size_t i = 0; i < n; i++)
     scanf("%d", &link[i]);

   for (int i = 0; i < n; i++) {
     for (int j = 0; j < n; j++) {
       scanf("%d", &map[i][j]);
     }
   }
   for (int i = 0; i < n; i++) {
     for (int j = i + 1; j < n; j++) {
       edge[nume++] = (E){i, j, map[i][j] + link[i] + link[j]};
     }
   }
   printf("%d\n", kruskal());
 }
 return 0;
}