今天做了数据结构的专项练习 题目是hdu1102  最开始没想明白，一直纠结于怎么把已经有的边并入最小树种

Problem DescriptionThere 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. InputThe 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. OutputYou 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 Input30 990 692990 0 179692 179 011 2

后来上网查了下 才想起要是两个村子本来有路的话 可以将他们的权值设为0 直接用prim做最小生成树即可。

突然觉得整条街的智商都被我拉低了

#include
      
       using namespace std;#include
       
        #define N 110#define MAX 0x7ffffffftypedef struct                                                //图用矩阵储存{    int mm[N][N];    int num;}diTu;typedef struct    c                                            //候选边，分别存权值与终点{    int len;    int end;}houxuan;void shuru( diTu & a, int n){    int i1, i2;    int n1 , i, j;    for( i1 = 1 ; i1 <= n; i1++)                            //下标从1开始方便点        for( i2 = 1; i2 <= n; i2++)            cin >> a.mm[i1][i2];    a.num = n;    cin >> n1;    while( n1--)    {        cin >> i >> j;                        a.mm[i][j] = 0;                                        //对于已经修好公路的情况 可看做两村庄距离为0        a.mm[j][i] = 0;    }}int prim( houxuan * h, diTu & a){    int i, j ,k , min;    int sum = 0;    int u = 1;    for( i = 1; i <= a.num; i++)                            //初始化候选边集    {        h[i].end = u;                                        //先以u为终点        h[i].len = a.mm[i][u];    }    h[u].len = -1;    for( k = 1; k < a.num ; k++)                            //找出n-1条最短边    {        min = MAX;        for( i = 1; i <= a.num; i++)        {            if( h[i].len >= 0 && h[i].len < min)            {                min = h[i].len;                                    j = i;            }        }        //cout << j << " 到 " <
        
         << endl;                //输出生成树的边        h[j].len = -1;                                        //顶点j并入集合 权值设置为负数避免重复选取                                                            //从j到j权值为0  将从j到end的权值设为负数时 确定新的候选边集        sum += min;        for( i = 1; i <= a.num ; i++)        {            if( a.mm[i][j] < h[i].len )                        //确定新的候选边集  此时h[j].len为负数             {                h[i].end = j;                h[i].len = a.mm[i][j];            }        }            }    return sum;}int main(){    diTu a;    houxuan * h;    int n;    while( cin >> n)                                                //这里要是用while(cin>>n)要按两下ctrl + z不知道为啥    {        h = (houxuan*) malloc((sizeof(houxuan))*(n +1));            //候选边集总共包含n条边 建立h[n]数组        shuru( a, n);        cout << prim( h, a) << endl;        free(h);    }    return 0;}