本文主要是介绍06-3. 公路村村通（30） 最小生成树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
06-3. 公路村村通（30）
时间限制
400 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
输入格式说明：
输入数据包括城镇数目正整数N（<=1000）和候选道路数目M（<=3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。
输出格式说明：
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出-1，表示需要建设更多公路。
样例输入与输出：
| 序号 | 输入 | 输出 |
| 1 | 6 15 1 2 5 1 3 3 1 4 7 1 5 4 1 6 2 2 3 4 2 4 6 2 5 2 2 6 6 3 4 6 3 5 1 3 6 1 4 5 10 4 6 8 5 6 3 | 12 |
| 2 | 3 1 2 3 2 | -1 |
| 3 | 5 4 1 2 1 2 3 2 3 1 3 4 5 4 | -1 |
提交代码
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define lson rt<<1,l,MID
#define rson rt<<1|1,MID+1,r
//#define lson root<<1
//#define rson root<<1|1
#define MID ((l+r)>>1)
typedef long long ll;
typedef pair<int,int> P;
const int maxn=3005;
const int base=1000;
const int inf=9999999999;
const double eps=1e-5;
long long cost[1005][1005];/矩阵存放图
long long d[maxn];
bool used[maxn];
int n,m;
long long prim()//prim算法
{for(int i=0;i<n;i++){d[i]=inf;used[i]=false;}d[0]=0;long long res=0;int cnt=0;while(true){int v=-1;for(int i=0;i<n;i++){if(!used[i]&&(v==-1||d[i]<d[v]))v=i;}if(v==-1)break;used[v]=true;res+=d[v];for(int i=0;i<n;i++)d[i]=min(d[i],cost[v][i]);}return res;
}bool vis[maxn];//dfs判断图是否是连通的
void dfs(int s)
{if(vis[s])return;vis[s]=1;for(int i=0;i<n;i++){if(!vis[i]&&cost[s][i]!=inf){//vis[i]=1;//不知道自己开始 怎么在这里写了这句 导致有组case一直过不去。。。。 dfs(i);}}
}int main()
{long long i,j,k,t;long long s,e;cin>>n>>m;for(i=0;i<n;i++)for(j=0;j<n;j++)cost[i][j]=inf;for(i=0;i<m;i++){cin>>s>>e>>t;--s;--e;if(cost[s][e]>t){cost[s][e]=t;}if(cost[e][s]>t){cost[e][s]=t;}}dfs(s);for(i=0;i<n;i++){if(vis[i]==false){printf("-1\n");return 0;}}printf("%lld\n",prim());return 0;
}这篇关于06-3. 公路村村通（30） 最小生成树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
