最小生成树、并查集算法题解

A. 最小生成树(要求用kruskal算法写)

Description

在一张图上有N个点，点与点之间的连接的花费都已经告诉你了，请你设计一下，如果解决这个“最小生成树”的问题。

Input

首先输入一个数字N（0〈=N〈=100）

​ 然后输入一个N*N的矩阵 其中第i行第j列的数字k表示从点i到点j需要的花费。

Output

一个数字，最少需要多少花费才能使得整张图任意两点都直接或者间接连通（也就是最小生成树的权）

Sample Input

5
0 41 67 34 0 
41 0 69 24 78 
67 69 0 58 62 
34 24 58 0 64 
0 78 62 64 0

0

2
0 1
1 0

Sample Output

116
0
1

Answer

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 101
struct TEdge {
	int nFrom;
	int nTo;
	int nCost;
};
void vInit(int nArr[],int nN);
int nInput(TEdge tArr[],int nN);
void vSort(TEdge tArr[],int nE);
bool bCmp(const TEdge &tA,const TEdge &tB);
int nKruskal(TEdge tArr[],int nArr[],int nN);
void vOut(int nOut);
void vMergeOwn(int nArr[],int nF,int nT,int nN);
int main() {
	int nNodes;
	int nEdges;
	TEdge tEdges[MAX*(MAX-1)/2+1];
	int nOwner[MAX];
	int nAns;
	while(cin >> nNodes) {
		vInit(nOwner,nNodes);
		nEdges=nInput(tEdges,nNodes);
		vSort(tEdges,nEdges);
		nAns=nKruskal(tEdges,nOwner,nNodes);
		vOut(nAns);
	}
	return 0;
}
void vInit(int nArr[],int nN) {
	int i;
	for(i=1; i<=nN; i++) {
		nArr[i]=i;
	}
}
int nInput(TEdge tArr[],int nN) {
	int nRet;
	int i,j;
	int nTemp;
	nRet=0;
	for(i=1; i<=nN; i++) {
		for(j=1; j<=nN; j++) {
			cin >> nTemp;
			if(i<j) {
				nRet++;
				tArr[nRet].nCost=nTemp;
				tArr[nRet].nFrom=i;
				tArr[nRet].nTo=j;
			}
		}
	}
//	返回边数 
	return nRet;
}
void vSort(TEdge tArr[],int nE) {
	sort(&tArr[1],&tArr[nE+1],bCmp);
}
bool bCmp(const TEdge &tA,const TEdge &tB) {
	return tA.nCost<tB.nCost;
}
int nKruskal(TEdge tArr[],int nArr[],int nN) {
	int nRet;
	int nCount;
	int nEdgeCnt;
	int nA,nB;
	nRet=0;
	nCount=nN;
	nEdgeCnt=1;
//	当集合个数大于 1 
	while(nCount>1) {
//		nA为起点的祖先 
		nA=nArr[tArr[nEdgeCnt].nFrom];
//		nB为终点的祖先 
		nB=nArr[tArr[nEdgeCnt].nTo];
		if(nA!=nB) {
			nRet+=tArr[nEdgeCnt].nCost;
//			合并集合，把起点的祖先都变为终点的祖先 
			vMergeOwn(nArr,nA,nB,nN);
//			合并后，集合个数减 1 
			nCount--;
		}
//		遍历所有边 
		nEdgeCnt++;
	}
	return nRet;
}
void vOut(int nOut) {
	cout << nOut << endl;
}
void vMergeOwn(int nArr[],int nF,int nT,int nN) {
	int i;
	for(i=1; i<=nN; i++) {
		if(nArr[i]==nT) {
			nArr[i]=nF;
		}
	}
}

B. 不同条件下的最小生成树

Description

课堂上我们学习了最小生成树的算法思想，也在实验课自己动手实现了这个算法，今天我们仍然要求来实现这个算法，只不过输入要求不一样，而且给定的图也不是所有顶点之间都有连接的边，有些顶点之间没有边，要求计算的最小费用也有点变化，请准确理解并求解.

Input

输入的第一行是测试数据的组数，对于每一组测试数据，有两部分，第一部分只有一行，分别有两个正整数nNode、nEdge（分别表示图的顶点数、边数，其中顶点编号为1到nNode，1<=nNode<=100）；第二部分共有nEdge行，每行有四个正整数nFrom、nTo、nDist、nV（分别表示这一条边的起始顶点、终止顶点、边的长度、这条边上能够承载的速度，当然它们的单位已经换算成相应的标准单位了，你不用考虑单位换算的问题；其中1<=nFrom，nTo<=nNode）。输入数据保证能够有生成树，每条边在计算费用时假设是各自的匀速运动。

Output

你的任务是以每条边上能承载的速度前提下将所需时间作为边的费用，求出最小生成树的花费，输出只有一行，即所求的花费，输出时保留一位小数。

Sample Input

1
6 10
1 2 6 3
1 3 1 1
1 4 5 2
2 3 5 3
2 5 3 2
3 4 5 3
3 5 6 3
3 6 4 2
4 6 2 1
5 6 6 3

Sample Output

7.8

Answer

#include <bits/stdc++.h>
using namespace std;
#define MAX 101
struct TEdge {
	int nFrom;
	int nTo;
	double nCost;
};
void vInit(int nArr[],int nN);
void vInput(TEdge tArr[],int nE);
void vSort(TEdge tArr[],int nE);
bool bCmp(const TEdge &tA,const TEdge &tB);
double nKruskal(TEdge tArr[],int nArr[],int nN);
void vOut(double nOut);
void vMerge(int nArr[],int nA,int nB,int nN);
int main() {
	int i;
	int nOwner[MAX];
	TEdge tEdges[MAX*(MAX-1)/2+1];
	int nCase,nNode,nEdge;
	double nAns;
	scanf("%d",&nCase);
	for(i=1; i<=nCase; i++) {
		scanf("%d%d",&nNode,&nEdge);
		vInit(nOwner,nNode);
		vInput(tEdges,nEdge);
		vSort(tEdges,nEdge);
		nAns=nKruskal(tEdges,nOwner,nNode);
		vOut(nAns);
	}
	return 0;
}
void vInit(int nArr[],int nN) {
	int i;
	for(i=1; i<=nN; i++) {
		nArr[i]=i;
	}
}
void vInput(TEdge tArr[],int nE) {
	int i;
	int nF,nT,nD,nV;
	for(i=1; i<=nE; i++) {
		scanf("%d%d%d%d",&nF,&nT,&nD,&nV);
		tArr[i].nCost=1.0*nD/nV;
		tArr[i].nFrom=nF;
		tArr[i].nTo=nT;
	}
}
void vSort(TEdge tArr[],int nE) {
	sort(&tArr[1],&tArr[nE+1],bCmp);
}
bool bCmp(const TEdge &tA,const TEdge &tB) {
	return tA.nCost<tB.nCost;
}
double nKruskal(TEdge tArr[],int nArr[],int nN) {
	double nRet;
	int nF,nT;
	int nCount;
	int nEdgeCnt;
	nRet=0.0;
	nCount=nN;
	nEdgeCnt=1;
	while(nCount>1) {
		nF=nArr[tArr[nEdgeCnt].nFrom];
		nT=nArr[tArr[nEdgeCnt].nTo];
		if(nF!=nT) {
			nRet+=tArr[nEdgeCnt].nCost;
			vMerge(nArr,nF,nT,nN);
			nCount--;
		}
		nEdgeCnt++;
	}
	return nRet;
}
void vOut(double nOut) {
	printf("%.1lf\n",nOut);
}
void vMerge(int nArr[],int nA,int nB,int nN) {
	int i;
	for(i=1; i<=nN; i++) {
		if(nArr[i]==nB) {
			nArr[i]=nA;
		}
	}
}

C. 图的连通性问题-并查集

Description

图论中有一个基本的问题，那就是一个无向图的连通性判别问题，今天我们就来讨论这个问题，我们知道，在计算机中一张图可以有两种表示方法，一是邻接矩阵二是邻接表，其中的邻接矩阵表示方法，我们已经在课堂上介绍最小生成树问题时讨论过，今天我们就来讨论用邻接表表示的图的连通性问题。要求用并查集方法求解。

Input

本问题有多组测试数据，每组测试数据有两部分，第一部分只有一行，是两个正整数，分别表示图的节点数N（节点编号从1到N，1<=N<=100）和图的边数E；第二部分共有E行，每行也是两个整数N1，N2（1<=N1，N2<=N），分别表示N1和N2之间有一条边。

Output

对于每一组测试数据，输出只有一行，如果是连通图，那么输出“Yes”，否则输出“No”。

Sample Input

6 10
1 2
1 3
1 4
1 5
1 6
2 3
2 4
3 4
3 5
3 6
4 3
1 2
1 3
2 3

Sample Output

Yes
No

Answer

#include<iostream>
using namespace std;
#define MAXN 1001
int nFather[MAXN],nSize[MAXN];
int nCount; 
void vMakeSet(int nS);
int nFindID(int nX);
void vUnion(int nA,int nB);
int main() {
	int i,n,m,u,v;
	while(cin>>n>>m) {
//		创建集合 
		vMakeSet(n);
		nCount=0;
		for(i=1; i<=m; i++) {
			cin>>u>>v;
			vUnion(u,v);
		}
		if(nCount+1==n) {
			cout<<"Yes"<<endl;
		} else {
			cout<<"No"<<endl;
		}
	}
	return 0;
}
void vMakeSet(int nS) {
	int i;
	for(i=1; i<=nS; i++) {
		nFather[i]=i;
		nSize[i]=1;
	}
}
//  寻找nX的祖先并把所有祖先的祖先都统一 
int nFindID(int nX) {
	if(nFather[nX]!=nX) {
		nFather[nX]=nFindID(nFather[nX]);
	}
	return nFather[nX];
}
void vUnion(int nA,int nB) {
	int nX,nY;
	nX=nFindID(nA);
	nY=nFindID(nB);
//	如果起点和终点的祖先不同，即不属于一个集合
	if(nX!=nY) {
//		把元素较少的集合合并到多的集合中 
		if(nSize[nX]<=nSize[nY]) {
			nFather[nX]=nY;
			nSize[nY]+=nSize[nX];
		} else {
			nFather[nY]=nX;
			nSize[nX]+=nSize[nY];
		}
		++nCount;
	}
}

D. 算法7-7,7-8：无向图的连通分量和生成树

Description

在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索的过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。

​ 对于非连通图，每个连通分量中的顶点集，和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。

​ 假设以孩子兄弟链表作为生成森林的存储结构，则生成非连通图的深度优先生成森林的算法可以描述如下：

而建立以p为根的深度优先生成树的算法可以描述如下：

在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立无向图的生成森林。对于森林中的每一棵生成树，遍历所有顶点，并输出遍历顶点的顺序。

Input

输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。

​ 以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个0或1，1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。

​ 输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图。

Output

每一行输出无向图中的一棵生成树，表示按照题目描述中的深度优先遍历算法遍历相应的连通分量的访问顶点顺序。每个整数后输出一个空格，并请注意行尾输出换行。

Sample Input

6
0 0 0 1 0 0
0 0 1 1 0 0
0 1 0 1 0 0
1 1 1 0 0 0
0 0 0 0 0 1
0 0 0 0 1 0

Sample Output

0 3 1 2 
4 5 

Hint

在本题中，需要掌握图的深度优先遍历的方法，并需要掌握无向图的连通性问题的本质。通过求出无向图的连通分量和对应的生成树，应该能够对图的连通性建立更加直观和清晰的概念。

Answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;

int nEdge[1005][1005];
bool bFlag[MAXN];
void vInit(int nN);
void vInput(int nN);
void vDFS(int nX,int nN);
void vOut(int nN);
int main() {
	int nN;
	cin>>nN;
	vInit(nN);
	vInput(nN);
	vOut(nN);
	return 0;
}
void vInit(int nN) {
	for(int i=1; i<=nN; i++) {
		bFlag[i]=false;
	}
}
void vInput(int nN) {
	for(int i=1; i<=nN; i++) {
		for(int j=1; j<=nN; j++) {
			scanf("%d",&nEdge[i][j]);
		}
	}
}
void vDFS(int nX,int nN) {
//	打印访问的结点
	printf("%d ",nX-1);
//	标记已访问
	bFlag[nX]=true;
	for(int i=1; i<=nN; i++) {
//		找出所有以nX为起点的边并对所有边的终点进行遍历 （递归）
		if(nEdge[nX][i]!=0&&bFlag[i]==false) {
			vDFS(i,nN);
		}
	}
}
void vOut(int nN) {
	for(int i=1; i<=nN; i++) {
//		若还未访问此节点，则为下一棵树
		if(bFlag[i]==false) {
			vDFS(i,nN);
			printf("\n");
		}
	}
}

E. 算法7-9：最小生成树

Description

最小生成树问题是实际生产生活中十分重要的一类问题。假设需要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然需要考虑这样一个问题，即如何在最节省经费的前提下建立这个通信网。

​ 可以用连通网来表示n个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，需要选择一棵生成树，使总的耗费最小。这个问题就是构造连通网的最小代价生成树，简称最小生成树。一棵生成树的代价就是树上各边的代价之和。

​ 而在常用的最小生成树构造算法中，普里姆（Prim）算法是一种非常常用的算法。以下是其算法的大致结构：

在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立最小生成树，并输出最小生成树的代价。

Input

输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。

​ 以后的n行中每行有n个用空格隔开的整数，对于第i行的第j个整数，如果不为0，则表示第i个顶点和第j个顶点有直接连接且代价为相应的值，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。

​ 输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图，且保证图中只有一个连通分量。

Output

只有一个整数，即最小生成树的总代价。请注意行尾输出换行。

Sample Input

4
0 2 4 0
2 0 3 5
4 3 0 1
0 5 1 0

Sample Output

6

Hint

在本题中，需要掌握图的深度优先遍历的方法，并需要掌握无向图的连通性问题的本质。通过求出无向图的连通分量和对应的生成树，应该能够对图的连通性建立更加直观和清晰的概念。

Answer

#include <bits/stdc++.h>
using namespace std;
#define MAX 101
#define INF 999999999
struct Tedge {
	int nP1;
	int nP2;
	int nW;
};
int nCost[MAX][MAX];
bool bV1[MAX],bV2[MAX];
void vInput(int nA);
int nPrim(int nA);
Tedge tGetEdge(int nA);
void vInit();
int main() {
	int n,nAns;;
	scanf("%d",&n);
	vInit();
	vInput(n);
	if(n!=0) {
		nAns=nPrim(n);
	} else {
		nAns=0;
	}
	printf("%d\n",nAns);

	return 0;
}
void vInit() {
	memset(bV1,false,sizeof(bV1));
	memset(bV2,true,sizeof(bV2));
}
void vInput(int nA) {
	int i,j;
	for(i=1; i<=nA; i++) {
		for(j=1; j<=nA; j++) {
			scanf("%d",&nCost[i][j]);
		}
	}
}
int nPrim(int nA) {
	int nRet,nC;
	Tedge tA;
	nRet=0;
	nC=1;
	bV1[1]=true;
	bV2[1]=false;
//	到最小生成树有nA个顶点为止
	while(nC<nA) {
		tA=tGetEdge(nA);
		bV1[tA.nP2]=true;
		bV2[tA.nP2]=false;
		nRet+=tA.nW;
		nC++;
	}
	return nRet;
}
Tedge tGetEdge(int nA) {
	Tedge tRet;
	int i,j,nF,nT,nMinV;
	nF=1;
	nT=1;
//	nMinV表示权值最小的边
	nMinV=INF;
	for(i=1; i<=nA; i++) {
//		如果顶点i在最小生成树中
		if(bV1[i]) {
			for(j=1; j<=nA; j++) {
//				且顶点j不在最小生成树中
				if(bV2[j]&&nCost[i][j]!=0) {
					if(nMinV>nCost[i][j]) {
						nMinV=nCost[i][j];
						nF=i;
						nT=j;
					}
				}
			}
		}
	}
	tRet.nP1=nF;
	tRet.nP2=nT;
	tRet.nW=nMinV;
	return tRet;
}

F. 通信系统

Description

某市计划建设一个通信系统。按照规划，这个系统包含若干端点，这些端点由通信线缆链接。消息可以在任何一个端点产生，并且只能通过线缆传送。每个端点接收消息后会将消息传送到与其相连的端点，除了那个消息发送过来的端点。如果某个端点是产生消息的端点，那么消息将被传送到与其相连的每一个端点。
为了提高传送效率和节约资源，要求当消息在某个端点生成后，其余各个端点均能接收到消息，并且每个端点均不会重复收到消息。
现给你通信系统的描述，你能判断此系统是否符合以上要求吗？

Input

输入包含多组测试数据。每两组输入数据之间由空行分隔。
每组输入首先包含2个整数N和M，N（1<=N<=1000）表示端点个数，M（0<=M<=N*(N-1)/2）表示通信线路个数。
接下来M行每行输入2个整数A和B（1<=A，B<=N），表示端点A和B由一条通信线缆相连。两个端点之间至多由一条线缆直接相连，并且没有将某个端点与其自己相连的线缆。
当N和M都为0时，输入结束。

Output

对于每组输入，如果所给的系统描述符合题目要求，则输出Yes，否则输出No。

Sample Input

4 3
1 2
2 3
3 4

3 1
2 3

0 0

Sample Output

Yes
No

Answer

#include<iostream>
using namespace std;
#define MAXN 1001
int nFather[MAXN],nSize[MAXN];
void vMakeSet(int nS);
int nFindID(int nX);
void nUnion(int nA,int nB);
bool bCheck(int nS);
int main() {
	int i,n,m,u,v;
	while(cin>>n>>m) {
		if(!n&&!m)
			return 0;
		vMakeSet(n);
		for(i=1; i<=m; i++) {
			cin>>u>>v;
			nUnion(u,v);
		}
		if(bCheck(n)&&m==n-1) {
			cout<<"Yes"<<endl;
		} else {
			cout<<"No"<<endl;
		}
	}
	return 0;
}
void vMakeSet(int nS) {
	int i;
	for(i=1; i<=nS; i++) {
		nFather[i]=i;
		nSize[i]=1;
	}
}
int nFindID(int nX) {
	if(nFather[nX]!=nX) {
		nFather[nX]=nFindID(nFather[nX]);
	}
	return nFather[nX];
}
void nUnion(int nA,int nB) {
	int nX,nY;
	nX=nFindID(nA);
	nY=nFindID(nB);
	if(nX!=nY) {
		if(nSize[nX]<=nSize[nY]) {
			nFather[nX]=nY;
			nSize[nY]+=nSize[nX];
		} else {
			nFather[nY]=nX;
			nSize[nX]+=nSize[nY];
		}
	}
}
bool bCheck(int nS) {
	int i;
	for(i=2; i<=nS; i++) {
		if(nFather[i]!=nFather[1]) {
			return false;
		}
	}
	return true;
}