#include<stdio.h>

struct TEdge {
    int a, b, dist;
};

int N, Q, adj[1000][1000];
int UFS[1000];
struct TEdge e[1000];
int num, ans;

int cmp(struct TEdge *a, struct TEdge *b)
{
    return (a -> dist - b -> dist);
}

int root(int i)
{
    if (UFS[i] == -1)
        return (i);
    else
        return (root(UFS[i]));
}

int equal(int i, int j)
{
    return (root(i) == root(j));
}

void _union(int i, int j)
{
    UFS[root(j)] = root(i);
}

int main()
{
    int i, j, a, b;
    
    scanf("%d", &N);
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            scanf("%d", &adj[i][j]);
    memset(UFS, -1, sizeof(UFS));
    scanf("%d", &Q);
    for (i = 0; i < Q; i++) {
        scanf("%d %d", &a, &b);
        if (!equal(a - 1, b - 1))
            _union(a - 1, b - 1);
    }
    
    num = 0;
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            if (adj[i][j]) {
                e[num].a = i;
                e[num].b = j;
                e[num].dist = adj[i][j];
                num++;
            }
    qsort(e, num, sizeof(e[0]), cmp);
    
    ans = 0;
    for (i = 0; i < num; i++)
        if (!equal(e[i].a, e[i].b)) {
            _union(e[i].a, e[i].b);
            ans += e[i].dist;
        }
        
    printf("%d\n", ans);
    
    system("pause");
    
    return (0);
}

• 谁能给举个反例呀？ (0) KingArthur 2007-07-18 21:42:36
• Re:高手帮忙解答，同样的疑问！为什么“用 Prim 都过了，Kruskal 咋不行啊？” (51) JohnHoward 2007-11-28 17:31:08
  • Re:高手帮忙解答，同样的疑问！为什么“用 Prim 都过了，Kruskal 咋不行啊？” (70) frkstyc 2007-11-28 17:32:05
  • Re:高手帮忙解答，同样的疑问！为什么“用 Prim 都过了，Kruskal 咋不行啊？” (55) 2432152240 2017-07-02 13:42:57
  • Re:高手帮忙解答，同样的疑问！为什么“用 Prim 都过了，Kruskal 咋不行啊？” (55) 2432152240 2017-07-02 14:02:56