2019-08-07

Prim方法的主要思想就是把所有的结点分为两类，一类是在树中的，另一类是不在树中的。
详情见：https://blog.csdn.net/luomingjun12315/article/details/47859993

There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected.
We know that there are already some roads between some villages and your job is the build some roads such that all the villages are connect and the length of all the roads built is minimum.

Input
The first line is an integer N (3 <= N <= 100), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 1000]) between village i and village j.
Then there is an integer Q (0 <= Q <= N * (N + 1) / 2). Then come Q lines, each line contains two integers a and b (1 <= a < b <= N), which means the road between village a and village b has been built.

Output
You should output a line contains an integer, which is the length of all the roads to be built such that all the villages are connected, and this value is minimum.
Sample Input
3
0 990 692
990 0 179
692 179 0
1
1 2
Sample Output
179

#include <iostream>
#include <cstring>      //memset函数的头文件
using namespace std;

#define MAXN 105
#define INF 0x3f3f3f      //表示无穷大
int map[MAXN][MAXN];
int dis[MAXN];
int visit[MAXN];     //标记已经在树中的点
int ans = 0;
int n, q;

void prim()
{
    memset(visit, 0, sizeof(visit));    //将visit数组中所有的元素初始化为0
    ans = 0;
    for(int i = 2; i <= n; i++)
        dis[i] = map[1][i];       //以1为根结点，dis中存储1到其他点的距离
    visit[1] = 1;
    for(int i = 1; i < n; i++)
    {
        int min = INF;
        int next = 0;
        for(int j = 2; j <= n; j++)
        {
            if(!visit[j] && min > dis[j])
            {
                min = dis[j];
                next = j;      //记录离树中的点距离最小的点，即下一个访问的点
            }
        }
        if(min == INF)
            return;
        visit[next] = 1;  //访问过的点标记为1
        ans += min;
        for(int j=2; j<=n; j++)   //假如树外的任一点离树中非根结点的距离
        {                        //要比根结点离树外结点的距离要小，更新dis的数据
            if(!visit[j] && dis[j] > map[next][j])
                dis[j] = map[next][j];
        }
    }
} 

int main()
{
    while(cin >> n && n >= 3)   //进行多项数据的输入
    {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                cin >> map[i][j];
        cin >> q;
    while(q--)
    {
        int a, b;
        cin >> a >> b;
        map[a][b] = 0;
        map[b][a] = 0;
    }
    prim();
    cout << ans << endl;
    }
    return 0;
}