网站遭攻击,如何利用fortran语言建设网站,网页图片素材,杭州低价做网站给定一个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行每行包含三个整数uvw表示点u和点v之间存在一条权值为w的边。 输出格式 共一行若存在最小生成树则输出一个整数表示最小生成树的树边权重之和如果最小生成树不存在则输出impossible。 数据范围 1≤n≤500 ,1≤m≤105 , 图中涉及边的边权的绝对值均不超过10000。 输入样例 4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4输出样例 6#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N501,INF0X3f3f3f3f;
int n,m,g[N][N],dis[N];
bool st[N];
void prim(){memset(dis,0x3f,sizeof(dis));int res0;for(int i0;in;i){int t-1;for(int j1;jn;j){if(!st[j](t-1||dis[t]dis[j]))tj;}if(idis[t]INF){coutimpossibleendl;return ;}if(i)resdis[t];for(int j1;jn;j)dis[j]min(dis[j],g[t][j]);st[t]true;}coutresendl;
}
int main(void){cinnm;memset(g,0x3f,sizeof(g));for(int i0,a,b,c;im;i){cinabc;g[a][b]g[b][a]min(g[a][b],c);}prim();return 0;
} 转载于:https://www.cnblogs.com/programyang/p/11197200.html
