Constructing Roads

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

分析：首先把已经有路的顶点放进集合中，然后再kruskal就行了。

注意要多组

C++版本一

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=100000+10;

int n,m,pre[N];
int find(int x)
{
    int r=x;
    while(pre[r]!=r)
        r=pre[r];
    return r;
}

void join(int x,int y)
{
    int fx,fy;
    fx=find(x);
    fy=find(y);
    if(fx!=fy)
        pre[fx]=fy;

}
struct node{
    int x,y,z;
    node(){};
    node(int a ,int b,int c){
        x=a;
        y=b;
        z=c;
    }
    bool operator <(const node &S)const{
        return z<S.z;
    }

}e[N];
int main()
{
    while(scanf("%d",&n)!=EOF){

    int a,b,c;
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&c);
            if(i>=j) continue;
            e[++cnt]=node(i,j,c);
        }
    }

    for(int i=1;i<=n;i++){
        pre[i]=i;
    }

    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        join(a,b);
    }

    sort(e+1,e+cnt+1);



    int ans=0;
    for(int i=1;i<=cnt;i++){
            //cout << e[i].x << endl;
        if(find(e[i].x)!=find(e[i].y)){
            join(e[i].x,e[i].y);
            ans+=e[i].z;
        }
    }
    cout << ans << endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define max 0x7fffffff
using namespace std;
 
struct edge
{
    int v1;
    int v2;
    int w;
}e[6000];//储存边
 
int cmp(const void *a,const void *b)
{
    struct edge *aa=(struct edge *)a;
    struct edge *bb=(struct edge *)b;
    if(aa->w != bb->w)
        return aa->w - bb->w;
    else
        return aa->v1 - bb->v1;//当权值相同时按顶点排序
}
 
int main()
{
    int n,q,a,b,map[101][101],vis[101],i,j,k,min;//map记录邻接矩阵，vis为顶点设置标志
    while(scanf("%d",&n)!=EOF)
    {
        min=0;
        for(i=1;i<=n;i++) vis[i]=i;//初始化vis，使各个顶点开始时各自属于独立的集合
        //输入邻接矩阵
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                scanf("%d",&map[i][j]);
            }
            map[i][i]=max;//自己到自己的路径修改为max
        }
        //输入已修好的路径
        scanf("%d",&q);
        for(i=1;i<=q;i++)
        {
            scanf("%d%d",&a,&b);
            map[a][b]=map[b][a]=0;
            //vis[b]=vis[a];
        }
        //将边的信息存入结构体e，注意只需存下三角形
        for(i=1,k=1;i<=n;i++)
        {
            for(j=1;j<=i;j++)
            {
               e[k].v1=i;
               e[k].v2=j;
               e[k].w=map[i][j];
               k++;
            }
        }
        //快排，因为从e[1]开始储存，故从e[1]开始排序
        qsort(&e[1],k-1,sizeof(e[1]),cmp);
        //生成树
        for(i=1,j=1;j<n;i++)
        {
            //两个顶点属于不同集合时表明边尚未加入树中
            if(vis[e[i].v1] != vis[e[i].v2])
            {
                //修改数值大的顶点的标志及其所有祖先的标志，将他们纳入树中
				int m=vis[e[i].v1]>vis[e[i].v2] ? vis[e[i].v2] : vis[e[i].v1];
				int M=vis[e[i].v1]>vis[e[i].v2] ? vis[e[i].v1] : vis[e[i].v2];
				for(int ii=1;ii<=n;ii++)
				{
					if(vis[ii]==M)
						vis[ii]=m;
				}
                min+=e[i].w;
                j++;
            }
        }
        printf("%d\n",min);
    }
    return 0;
}

C++版本三

先把已经建好的路加到树里面，在利用最小生成树模板。

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
 
const int MAX=10000+10;
int par[MAX],value[MAX][MAX];
int n,m;
int ant=0;
int ans=0;
int k=0;
 
struct node{
	int x,y;
	int val;
}road[100010];
 
bool cmp(node a,node b){
	return a.val<b.val;
}
 
void init(int v){
	for(int i=0;i<=v;i++)
	par[i]=i;
}
 
int find(int x){
	return x==par[x]?x:par[x]=find(par[x]);
}
 
bool unite(int a,int b){
	int fa=find(a);
	int fb=find(b);
	if(fa!=fb){
		par[fa]=fb;
		return true;
	}
	return false;
}
 
void kruskal(){
	ans=0;
	for(int i=0;i<k;i++){
		if(ant==n-1)
		break;
		if(unite(road[i].x,road[i].y)){
			ant++;
			ans+=road[i].val;
		}
	}
}
 
int main(){
	while(cin>>n){
		init(n);
		k=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				cin>>road[k].val;
				road[k].x=i;
				road[k].y=j;
				k++;
			}
		}
		int q;
		ant=0;
		cin>>q;
		for(int i=0;i<q;i++){
			int a,b;
			cin>>a>>b;
			if(unite(a,b))
			ant++;
		}
		sort(road,road+k,cmp);
		kruskal();	
		cout<<ans<<endl;
	}
	return 0;
}

C++版本四

prim算法

#include <iostream>
#include <cstring>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

int Map[105][105],visit[105],dis[105],M;
void prim()
{
    for(int i = 1;i <= M; i++)
    {
        dis[i] = Map[1][i];
    }
    //dis[1] = 0;
    //visit[1] = 1;
    int sum = 0;
    for(int i = 1; i <= M; i++)
    {
        int temp = INF,pos;
        for(int j= 1; j <= M; j++)
        {
            if(!visit[j] && temp > dis[j])
            {
                temp = dis[j];
                pos = j;
            }
        }
        //if(temp == INF)return 0;
        visit[pos] = 1;
        sum += dis[pos];
        for(int j = 1; j <= M; j++)
        {
            if(!visit[j] && Map[pos][j] < dis[j])
            {
                dis[j] = Map[pos][j];
            }
        }
    }
    printf ("%d\n",sum);
}
int main()
{
    while (~scanf("%d",&M))
    {
    //memset(Map,0x3f,sizeof(Map));
    //memset(dis,0x3f,sizeof(dis));
    memset(visit,0,sizeof(visit));

    for (int i=1; i<=M; i++)
    {
        for (int j=1; j<=M; j++)
        {
            scanf("%d",&Map[i][j]);
        }
    }
    int N;
    scanf ("%d",&N);
    for (int i=0; i<N; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        Map[a][b] = Map[b][a] = 0;
    }
    prim();
    }
}

C++版本五

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int pre[550],zz[550],ma[550][550];
struct node
{
	int u,v,w;
}s[125010];
bool cmp(node a,node b)
{
	return a.w<b.w;
}
int find(int x)
{
	if(pre[x]==x)
		return x;
	return pre[x]=find(pre[x]);
}
void merge(int x,int y)
{
	int fx=find(x),fy=find(y);
	if(fx==fy)
		return ;
	if(zz[fx]<zz[fy]) pre[fx]=fy;
	else
	{
		pre[fy]=fx;
		if(zz[fx]==zz[fy]) zz[fx]++;
	}
}
int main()
{
		int t,n,q,x,y;
	while(~scanf("%d",&n))
	{
		for(int i=1;i<=n;i++)
		{
			pre[i]=i;
			zz[i]=0;
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&ma[i][j]);
		scanf("%d",&q);
		for(int i=0;i<q;i++)
		{
			scanf("%d %d",&x,&y);
			ma[x][y]=0;
			ma[y][x]=0;
		}
		int l=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=i;j++)
			{
				if(i==j) continue;
				s[l].u=i;
				s[l].v=j;
				s[l].w=ma[i][j];
				l++;
			}
		}
		sort(s,s+l,cmp);
		int ans=0;
		for(int i=0;i<l;i++)
		{
			if(find(s[i].u)!=find(s[i].v))
			{
				ans+=s[i].w;
				merge(s[i].u,s[i].v);
			}
		}
		printf("%d\n",ans);
	}
	return 0; 
}