本文主要是介绍hdu 1879题解报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
-hdu- 1879 题解报告
题目大意：给定n个点以及n*(n-1)/2条边的信息，然后让我们求出最短的路程使得所有点相通。
题目解析：其实就是一个最小生成树的问题，这里我用的是prime算法。
实现代码：
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 150;
const int INF = 0xfffffff;
int n, ans; //ans为最终答案
int tag[maxn]; //标记数组，标记第i个顶点是否已经被选择，1表示已经被选中
int map[maxn][maxn]; //存放边的权值的信息，路已建的为0，不通的为无穷远INF，待建的为某个正值
void addEdge(int a, int b, int d, intt){ //添加边权值的函数
if(t == 0 ) map[a][b] = map[b][a] = d;
elsemap[a][b] = map[b][a] = 0;
}
void prime(){ //求解最小生成树问题的prime算法
intdist[maxn]; //dist[i]存放第i个顶点到已选点集的最短距离
memset(dist,INF, sizeof(dist));
memset(tag,0, sizeof(tag));
tag[0]= 1; //第0个点作为源点，自动进入已选点集中
for(inti = 0; i < n; i ++){
dist[i]= map[0][i]; //所有点到已选点集的最短距离dist【i】容易得到
}
intindex = 0, min;
ans= 0; //ans记录的是最小生成树的所有边的权值之和
while(1){ //直到所有点都在已选点集中循环才终止，即min一直等于INF时
min= INF;
for(intj=1; j < n; j ++){ //扫描出此时未选中的点当中最小的dist【i】值
if(!tag[j] && dist[j] < min){
min= dist[j];
index= j;
}
}
if(min== INF) break;
tag[index]= 1; //新选入的点tag改变
ans+= min; //权值之和增加min值
for(intj = 1; j < n; j ++){ //有新的点被选中后重新刷新一遍dist数组
if(map[index][j]< dist[j]) dist[j] = map[index][j];
}
}
}
int main()
{
inta, b, dis, t;
while(scanf("%d",&n) != EOF){
if(n== 0) break;
memset(map,INF, sizeof(map));
for(inti = 0; i < n*(n-1)/2; i ++){
scanf("%d%d%d%d",&a, &b, &dis, &t);
addEdge(a-1,b-1, dis, t);
}
prime();
printf("%d\n",ans);
}
return0;
}
这篇关于hdu 1879题解报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
