1074.安全网络 ver.1

#include <cstdio>
#include <cstdlib>
#include <iostream>
#define inf 0x3fffffff
using namespace std;

bool b[101];
int a[101][101];
int c[101];
int n;

int prim() {
    int i, j, s, t, len = 0;

    for (i = 1; i <= n; i++) {
        c[i] = a[1][i];
        b[i] = false;
    }
    b[1] = true;

    for (i = 2; i <= n; i++) {
        t = 1;
        s = inf;
        for (j = 2; j <= n; j++) {
            if (b[j] || c[j] > s)
                continue;
            t = j;
            s = c[j];
        }
        len += s;
        b[t] = true;
        for (j = 2; j <= n; j++)
            if (!b[j] && c[j] > a[t][j])
                c[j] = a[t][j];
    }
    return len;
}

int main(int argc, char* argv[]) {
    int i, j;

    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);

    printf("%d\n", prim());

    return 0;
}