Constructing Roads POJ

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

题意：有不超过100个村庄，输入第一行一个数n表示村庄数，然后有n行每行都是第i个村庄与其他村庄的之间的距离，然后再一行有一个数m表示已经修建的道路数，然后往下m行，每行两个数表示在这两个村庄之间已经修建好了道路。
问在让所有的村庄都能够连接在一起的前提下至少还要修建多长的道路。

思路：题意可以以变换一下，已经修建好道路的村庄之间是可以不用再连接这两个村庄的，所以我们只需要求剩下的没连接在一起村庄进行最小生成数算法。

首先对村庄间的距离用一个二维数组保存，然后对已经修建好的村庄之间的道路进行标记，再对二维数组到容器的转发中把已经连在一起的村庄合并并不录入这个数据，最后在根据Kruskal算法进行运算。

代码：

#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <iostream>
#define mod 998244353
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

//u表示起点，v表示终点，cost表示花费
struct node
{
    int u,v;
    double cost;
};
//排序，从小到大
bool cmp(node a,node b)
{
    return a.cost<b.cost;
}
//存放边的信息
vector<node> ve;

//fa表示当前i的最远祖先
int fa[110];
//初始化fa，开始时自己是自己的祖先
void init(int qwq)
{
    for(int i=0;i<=qwq;i++)
    {
        fa[i]=i;
    }
}
//查找最远祖先，同时进行路径压缩
int find(int x)
{
    if(fa[x]==x)
    {
        return x;
    }
    return fa[x]=find(fa[x]);
}
//判断最远祖先是否相同
bool che(int x,int y)
{
    return find(x)==find(y);
}
//合并x,y，把他们放到同一个家族中
void mer(int x,int y)
{
    if(!che(x,y)) 
    {
        fa[fa[x]]=fa[y];
    }
    return ;
}
int n,m;
//ma用于保存村庄之间的距离
int ma[105][105];
//bj用于标记已经连接的村庄编号
int bj[105][105];
int main()
{
    scanf("%d",&n);
    //初始化
    init(n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&m);
            ma[i][j]=m;
        }
    }
    int a,b;
    //初始化bj
    memset(bj,0,sizeof(bj));
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d %d",&a,&b);
        //标记，
        bj[a][b]=1;
        bj[b][a]=1;
    }
    node no;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            //当村庄之间没有道路时
            if(bj[i][j]==0)
            {
                no.u=i;
                no.v=j;
                no.cost=ma[i][j];
                ve.push_back(no);
            }
            else
            {//当村庄之间有道路时，合并这两个村庄
                mer(i,j);
            }
        }
    }
    int ans=0;
    //排序
    sort(ve.begin(),ve.end(),cmp);
    for(int i=0;i<ve.size();i++)
    {
        //当两个村庄之间没有连接时
        if(!che(ve[i].u,ve[i].v))
        {
            //合并
            mer(ve[i].u,ve[i].v);
            ans+=ve[i].cost;
        }
    }
    printf("%d
",ans);
    //清除容器内存
    ve.clear();
}