这题显然还是用prim，经过优化后的prim效率可以达到O(n²)。

离省赛越来越近，我也越来越没有状态，这种小白题从昨天晚上开始做，做到断网；今天爬起来继续做，才发现是把a[i][k]赋值 无限大的条件写错了——无良的出题者居然加入了两个端点间距离可能为0的情况......

#include <cstdio>
#include <string>

int a[1010][1010], s[1010], dis[1010], t, n;

void pd ()
{
    int i;
    for ( i = 0; i < n; i ++ )
    {
        printf ( "%d ", dis[i] );
    }
    printf ( "\n" );
}

void init ()
{
    int i, k;
    scanf ( "%d", &n );
    for ( i = 0; i < n; i ++ )
    {
        scanf ( "%d", &s[i] );
    }
    for ( i = 0; i < n; i ++ )
    {
        for ( k = 0; k < n; k ++ )
        {
            scanf ( "%d", &a[i][k] );
            if ( i == k )
            {
                a[i][k] = 9999;
            }
            else
            {
                a[i][k] += s[i] + s[k];
            }
        }
    }
    memset ( dis, 0, sizeof ( dis ) );
}

void prim ()
{
    int i, k, sum = 0;
    dis[0] = -1;
    for ( i = 1; i < n; i ++ )
    {
        dis[i] = a[0][i];
    }
    for ( i = 1; i < n; i ++ )
    {
        //pd ();
        int mx = 9999, j;
        for ( k = 0; k < n; k ++ )
        {
            if ( dis[k] != -1 && dis[k] < mx )
            {
                j = k;
                mx = dis[k];
            }
        }
        sum += mx;
        dis[j] = -1;
        for ( k = 0; k < n; k ++ )
        {
            if ( a[j][k] < dis[k] )
            {
                dis[k] = a[j][k];
            }
        }
    }
    printf ( "%d\n", sum );
}

int main ()
{
    //freopen ( "in.txt", "r", stdin );
    scanf ( "%d", &t );
    int i;
    for ( i = 0; i < t; i ++ )
    {
        init ();
        prim ();
    }
    return 0;
}

评论