会python真的可以为所欲为0(回)
359天前
这里还有人吗1(回)
544天前这里还有人吗0(回)
544天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
769天前到处都是羊，不想上班0(回)
849天前
鸽子
0(回)
853天前
最小生成树（kruskal）.rar(免费下载)[2 次下载]#include<stdio.h> |
#include<string.h> |
#include<algorithm> |
using namespace std; |
const int maxn = 5005; |
struct Edge |
{ |
int u; |
int v; |
int val; |
bool operator < (const Edge &b)const |
{ |
return val < b.val; |
} |
}edge[maxn]; |
int n; |
int father[105]; |
int find(int x) |
{ |
int r = x; |
while(r != father[r]) |
r = father[r]; |
int i = x,t; |
while(i != r) |
{ |
t = father[i]; |
father[i] = r; |
i = t; |
} |
return r; |
} |
void mix(int x,int y) |
{ |
int fx = find(x); |
int fy = find(y); |
if(fx != fy) |
father[fx] = fy; |
} |
int kruskal(int e) |
{ |
int ans = 0; |
int cnt = 0; |
for(int i = 0;i < e;i++) |
{ |
if(find(edge[i].u) != find(edge[i].v)) |
{ |
cnt++; |
mix(edge[i].u,edge[i].v); |
ans += edge[i].val; |
} |
if(cnt == n-1) |
break; |
} |
return ans; |
} |
int main() |
{ |
while(scanf("%d",&n) != EOF && n) |
{ |
for(int i = 1;i <= n;i++) |
father[i] = i; |
int e = n*(n-1)/2; |
for(int i = 0;i < e;i++) |
{ |
int is; |
scanf("%d%d%d%d",&edge[i].u,&edge[i].v,&edge[i].val,&is); |
if(is) |
edge[i].val = 0; |
} |
sort(edge,edge+e); |
printf("%d\n",kruskal(e)); |
} |
return 0; |
} |
最小生成树（kruskal）.rar(免费下载)[2 次下载]
