社区讨论

prim 求助,样例能过但wa

P3366【模板】最小生成树参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo2wyye0
此快照首次捕获于
2023/10/23 21:08
2 年前
此快照最后确认于
2023/10/23 21:08
2 年前
查看原帖
1)对于重边选择了最小的那一个
C
#include<iostream>
#include<algorithm>
using namespace std;
const int maxs = 50;
const int INF = 99999;
struct AMGraph {
	int vexs[maxs];//定点表
	int arr[maxs][maxs];//邻接矩阵
	int vexnum, arcnum;//顶点数,边数
};
void initGraph(AMGraph &G) {
	cin >> G.vexnum >> G.arcnum;
	for (int i = 1; i <= G.vexnum; i++) {
		G.vexs[i] = i;
	}
	for (int i = 1; i <= G.vexnum; i++) {
		for (int j = 1; j <= G.vexnum; j++) {
			G.arr[i][j] = INF;
		}
	}
}
void createGraph(AMGraph& G) {
	int i = 0, j = 0,w=0;
	for (int k = 1; k <= G.arcnum; k++) {
		cin >> i >> j>>w;
		if (w < G.arr[i][j]) {
			G.arr[i][j] = w;
		}
	}
}
void showGraph(AMGraph G)
{
	for (int i = 1; i <= G.vexnum; i++)
	{
		for (int j = 1; j <= G.vexnum; j++)
		{
			if (G.arr[i][j] == INF)	//无穷大弄得更好看点
				cout << "∞" << " ";
			else
				cout << " " << G.arr[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}
int d[maxs];//顶点与集合s的最短距离
int visit[maxs];//标志数组
int res = 0;//最小生成树的边权值
void prim(AMGraph& G) {
	//把数组初始化一下,除了1之外所有点到s集合的距离都是无穷
	fill(d + 1, d + G.vexnum + 1, INF);
	d[1] = 0;//一开始只有1和S集合距离为0
	visit[1] = 1;
	//用初始点的路径更新d数组
	for (int i = 2; i <= G.vexnum; i++) {
		d[i] = min(d[i], G.arr[1][i]);
	}
	for (int i = 2; i <= G.vexnum; i++) {
		int temp =INF;
		int t = -1;
		//找数组中距离s最小且没有加入集合s的点
		for (int j = 2; j <= G.vexnum; j++) {
			if (visit[j] == 0 && d[j] < temp) {
				temp = d[j];
				t = j;
			}
		}
		if (t == -1) {//找不到说明不是连通图
			res = INF;
			return;
		}
		visit[t] = 1;
		res += d[t];
		for (int j = 2; j <= G.vexnum; j++) {
			
			d[j] = min(d[j], G.arr[t][j]);
		}
	}
	if (res == INF) {
		cout << "orz";
	}
	else {
		cout << res;
	}
	
}
int main() {
	AMGraph G;
	initGraph(G);
	createGraph(G);
	showGraph(G);
	prim(G);
}

回复

0 条回复,欢迎继续交流。

正在加载回复...