会python真的可以为所欲为0(回)
362天前
这里还有人吗1(回)
548天前这里还有人吗0(回)
548天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
772天前到处都是羊，不想上班0(回)
852天前
鸽子
0(回)
856天前
最小生成树（prim）.rar(免费下载)[0 次下载]#include<stdio.h> |
#include<string.h> |
#include<math.h> |
const int maxn = 100 + 5; |
const int INF = 1e9; |
int x[maxn]; |
int y[maxn]; |
int vis[maxn]; |
double low[maxn]; |
double G[maxn][maxn]; |
double prim(int n) |
{ |
double res = 0; |
double min; |
int i,j,pos; |
vis[1] = 1; |
pos = 1; |
for(i = 1; i <= n; i++) |
if(i != pos) low[i]=G[pos][i]; |
for(i=1; i<n; i++) |
{ |
min=INF; |
for(j=1; j<=n; j++) |
{ |
if(vis[j]==0&&min>low[j]) |
{ |
min=low[j]; |
pos=j; |
} |
} |
if(min == INF) |
break; |
res += min; |
vis[pos]=1; |
for(j=1; j<=n; j++) |
if(vis[j]==0 && low[j]>G[pos][j]) |
low[j]=G[pos][j]; |
} |
if(i != n) |
return -1; |
return res; |
} |
int main() |
{ |
int T; |
scanf("%d",&T); |
while(T--) |
{ |
memset(G,0,sizeof(G)); |
memset(vis,0,sizeof(vis)); |
int n,e; |
scanf("%d",&n); |
for(int i = 1; i <= n; i++) |
{ |
scanf("%d%d",&x[i],&y[i]); |
for(int j = 1; j < i; j++) |
{ |
double t = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]); |
t = sqrt(t); |
if(t >= 10.0 && t <= 1000.0) |
G[i][j] = G[j][i] = t; |
else |
G[i][j] = G[j][i] = INF; |
} |
} |
double ans = prim(n); |
ans *= 100; |
if(ans > 0) |
printf("%.1lf\n",ans); |
else |
printf("oh!\n"); |
} |
return 0; |
} |
最小生成树（prim）.rar(免费下载)[0 次下载]
