【prim】wikioi1003

1003 电话连线

题目描述 Description

一个国家有n个城市。若干个城市之间有电话线连接，现在要增加m条电话线（电话线当然是双向的了），使得任意两个城市之间都直接或间接经过其他城市有电话线连接，你的程序应该能够找出最小费用及其一种连接方案。

输入描述 Input Description

输入文件的第一行是n的值（n<=100）. 第二行至第n+1行是一个n*n的矩阵，第i行第j列的数如果为0表示城市i与城市j有电话线连接，否则为这两个城市之间的连接费用（范围不超过10000）。

输出描述 Output Description

输出文件的第一行为你连接的电话线总数m，第二行至第m+1行为你连接的每条电话线，格式为i j，（i<j）， i j是电话线连接的两个城市。输出请按照Prim算法发现每一条边的顺序输出，起始点为1

第m+2行是连接这些电话线的总费用。

样例输入 Sample Input

5

0 15 27 6 0

15 0 33 19 11

27 33 0 0 17

6 19 0 0 9

0 11 17 9 0

样例输出 Sample Output

2

1 4

2 5

17

数据范围及提示 Data Size & Hint

n<=100

又是不想读英语题……prim是必然的，它说了要按Prim算法发现每一条边的顺序输出

我是个渣渣，每次遇到输方案一定要折腾一会才得行，即使是如此弱逼的输方案……

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long n;
long a[110][110];
long dist[110];
bool v[110];
long edge[110][2];
long pre[110];
long const INF = 1000000;

void prim()
{

    memset(v, 0, sizeof(v));
    v[1] =  1;
    for (long i = 1; i <= n; i++)
    {
        dist[i] = a[1][i];
        pre[i] = 1;
    }
    long sum = 0;
    long cnt = 0;
    for (long k = 1; k < n; k++)
    {
        long minn = INF;
        long point = 0;
        for(long i = 1; i <= n; i++)
        {
            if((!v[i]) && (dist[i] < minn))
            {
                minn = dist[i];
                point = i;
            }
        }

        v[point] = true;
        sum += dist[point];

        if (dist[point] != 0)
        {
            cnt++;
            edge[cnt][0] = pre[point];
            edge[cnt][1] = point;
        }
        dist[point] = INF;
        for (long i = 1; i <= n; i++)
        {
            if (!v[i]&&(a[point][i] < dist[i]))
            {
                dist[i] = a[point][i];
                pre[i] = point;
            }

        }
    }

    printf("%d\n", cnt);
    for (long i = 1; i <= cnt; i++)
    {
        if (edge[i][0] < edge[i][1])
            printf("%d %d\n", edge[i][0], edge[i][1]);
        else printf("%d %d\n", edge[i][1], edge[i][0]);
    }
    printf("%d\n", sum);

}

int main()
{
    freopen("1003.in", "r", stdin);
    scanf("%d\n", &n);

    for (long i = 1; i <= n; i++)
    for (long j = 1; j <= n; j++)
        scanf("%d ", &a[i][j]);

    prim();
    return 0;
}