版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/46380521

题目连接： http://www.lightoj.com/volume_showproblem.php?problem=1040

题意也不说了。

水题

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <math.h>
#include <ctype.h>
#include <time.h>
#include <queue>
#include <iterator>
#include <vector>
#include <set>

using namespace std;

const int MAXN = 55;
const int inf = 100000000;

int p[MAXN][MAXN];
int n;

int dis[MAXN], v[MAXN];
int prim(int map[][55], int n)
{
    memset(v, 0, sizeof(v));
    int min, sum = 0;
    for (int i = 0; i < n; i++)
        dis[i] = map[0][i];
    v[0] = 1;
    for (int i = 1; i < n; i++)
    {
        int k = -1;
        min = inf;
        for (int j = 0; j < n; j++)
            if (!v[j] && min>dis[j])
            {
                k = j;
                min = dis[j];
            }
        if (k == -1)
            return - 1;
        sum += min;
        v[k] = 1;
        for (int j = 0; j < n; j++)
            if (!v[j] && dis[j]>map[k][j])
                dis[j] = map[k][j];
    }
    return sum;
}

void init()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i != j && p[i][j] == 0 && p[j][i] == 0)
            {
                p[i][j] = p[j][i] = inf;
            }
        }
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    for (int cases = 1; cases <= t; cases++)
    {
        int ans = 0;
        memset(p,0,sizeof(p));
        scanf("%d",&n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                scanf("%d",&p[i][j]);
                ans += p[i][j];
                if (i == j)
                    p[i][i] = 0;
                if (i!=j && p[i][j] == 0)
                {
                    p[i][j] = p[j][i];
                }
                else if (i != j && p[j][i] != 0 && p[i][j]!=0)
                {
                    p[i][j] = p[j][i] = min(p[i][j], p[j][i]);
                }
                else if (i != j && p[j][i] == 0)
                {
                    p[j][i] = p[i][j];
                }
            }
        init();
        int tmp = prim(p, n);
        ans -= tmp;
        if (tmp!=-1)
            printf("Case %d: %d\n",cases,ans);
        else
            printf("Case %d: -1\n", cases);
    }
    return 0;
}