大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
最小生成树问题。
矩阵输入。
这只是很伤心G++ 服从AC。
。
C++ 已经RE。
唯一的问题,说的最多的 100 X 100 矩阵啊。
Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others.
→_→ 不知各位怎么理解这句。
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<queue> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 using namespace std; int n; struct lx { int u,v,len; } l[500*1001]; int fa[1001]; bool cmp(lx a,lx b) { return a.len<b.len; } int father(int x) { if(x!=fa[x]) return fa[x]=father(fa[x]); } int main() { while(scanf("%d",&n)!=EOF) { for(int i=0; i<=n; i++) fa[i]=i; int cot=0; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) { int len; scanf("%d",&len); if(i==j)continue; l[cot].u=i; l[cot].v=j; l[cot++].len=len; } sort(l,l+cot,cmp); int ans=0; for(int i=0; i<cot; i++) { int fu=father(l[i].u); int fv=father(l[i].v); if(fu==fv)continue; fa[fv]=fu; ans+=l[i].len; } printf("%d\n",ans); } }
版权声明:本文博主原创文章,博客,未经同意不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116986.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...