Eddy’s picture

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;

int n;
double g[N][N];
double dist[N];
bool st[N];

struct node {
    double x;
    double y;
} spot[N];

double prim() {
    memset(dist, 0, sizeof dist);
    memset(st, false, sizeof st);

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

        dist[i] = g[1][i];
    st[1] = true;
    double res = 0;

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

        int t = -1;

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

            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        res += dist[t];
        st[t] = true;

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

            dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; i ++ )

            scanf("%lf%lf", &spot[i].x, &spot[i].y);

        memset(g, 0, sizeof g);

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

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

                if (i != j)
                    g[i][j] = g[j][i] = sqrt(pow(spot[i].x - spot[j].x, 2) + pow(spot[i].y - spot[j].y, 2));
        printf("%.2lf\n", prim());
    }

    return 0;
}

畅通工程

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;

#define INF 0x3f3f3f3f

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim() {
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    int res = 0;

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

        int t = -1;

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

            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF)
            return INF;

        if (i)
            res += dist[t];
        st[t] = true;

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

            dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main() {
    while (~scanf("%d%d", &m, &n)) {
        if (m == 0)
            break;
        memset(g, 0x3f, sizeof g);

        while (m -- ) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g[a][b] = g[b][a] = min(g[a][b], c);
        }

        if (prim() == INF)
            puts("?");
        else
            printf("%d\n", prim());
    }

    return 0;
}

Jungle Roads

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;

#define INF 0x3f3f3f3f

int n;
int g[N][N];
int dist[N];
bool st[N];

int prim() {
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    int res = 0;

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

        int t = -1;

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

            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF)
            return INF;

        if (i)
            res += dist[t];
        st[t] = true;

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

            dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main() {
    while (~scanf("%d", &n)) {
        if (n == 0)
            break;
        memset(g, 0x3f, sizeof g);
        char a, b;
        int m, c;

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

            scanf("%s%d", &a, &m);
            a = a - 'A' + 1;

            for (int j = 1; j <= m; j ++ ) {


                scanf("%s%d", &b, &c);
                b = b - 'A' + 1;
                g[a][b] = g[b][a] = min(g[a][b], c);
            }
        }

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

    return 0;
}

Constructing Roads

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

#define INF 0x3f3f3f3f

int n;
int g[N][N];
int dist[N];
bool st[N];

int prim() {
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    int res = 0;

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

        int t = -1;

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

            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF)
            return INF;

        if (i)
            res += dist[t];
        st[t] = true;

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

            dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main() {
    while (~scanf("%d", &n)) {
        memset(g, 0, sizeof g);

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

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

                scanf("%d", &g[i][j]);
        int q;
        scanf("%d", &q);

        while (q -- ) {
            int a, b;
            scanf("%d%d", &a, &b);
            g[a][b] = g[b][a] = 0;
        }

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

    }

    return 0;

}