这题显然还是用prim，经过优化后的prim效率可以达到O(n2)。 离省赛越来越近，我也越来越没有状态，这种小白题从昨天晚上开始做，做到断网；今天爬起来继续做，才发现是把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;}

评论