交做网站视频百度云,wordpress定时插件,wordpress 百度云网盘,frontpage怎么改网站名字题目
给定一个 n 个点 m 条边的无向图#xff0c;图中可能存在重边和自环#xff0c;边权可能为负数。
求最小生成树的树边权重之和#xff0c;如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G(V,E)#xff0c;其中 V 表示图中点的集合#xff0c;E…题目
给定一个 n 个点 m 条边的无向图图中可能存在重边和自环边权可能为负数。
求最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G(V,E)其中 V 表示图中点的集合E 表示图中边的集合n|V|m|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行每行包含三个整数 u,v,w表示点 u 和点 v 之间存在一条权值为 w 的边。
输出格式
共一行若存在最小生成树则输出一个整数表示最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。
数据范围
1≤n≤500 1≤m≤10^5 图中涉及边的边权的绝对值均不超过 10000
思路 建立一个集合将距离这个集合最近的节点s放入集合内部然后使用节点s对其他节点到集合的距离进行更新st[s]true表示节点s已经被放入集合已经放入集合的元素不能再次被放入集合。然后开始下一次循环每次放入一个节点到集合中一共遍历n次一共n个点。
代码
#includebits/stdc.h
#define N 510
using namespace std;
const int INF 0x3f3f3f3f;
int n,m;// n个点m条边
int g[N][N];// 表示点i到点j的距离不邻接的话为正无穷
int dist[N];// 表示点i到集合的最小距离
bool st[N];// 表示点i是否在集合内部int prim()
{memset(dist,0x3f,sizeof(dist));// 将距离初始化为正无穷int res 0;for(int i 0; i n; i )// 遍历n个点{int t -1;for(int j 1; j n; j )// 遍历所有点if(!st[j] (t -1 || dist[t] dist[j]))// 找到不在集合内部并且距离集合最近的点t j;if(i dist[t] INF) return INF; // 如果找不到距离小于正无穷的点则代表这个图不连通没有最小生成树当i等于零时集合还没有元素不能进行判断if(i) res dist[t];// 将这条最小边加起来是建成最小生成树的其中一条边当i等于零时集合还没有元素不能进行判断for(int j 1;j n; j ) dist[j] min(dist[j],g[t][j]);// 使用这个点对这其他点进行更新st[t] true;// 这个点已经在集合内部了}return res;// 返回最小生成树的长度
}int main()
{cin n m;// 输入点数边数memset(g,0x3f,sizeof(g));while(m --){int a,b,c;cin a b c;// 输入点a到点b之间的距离g[a][b] g[b][a] min(g[a][b],c);// 建立无向图}int t prim();if( t INF ) cout impossible endl;else cout t endl;return 0;
}
