题目
P2330 [SCOI2005]繁忙的都市
分析
prim算法模板，当然也可以用Kruskal算法做
AC代码
#include <iostream>
using namespace std
;
int n
, m
, ans
, cnt
;
int dis
[10005], vis
[10005], head
[10005];
struct Edge
{
int to
;
int w
;
int next
;
}edge
[100005 << 1];
void add(int u
, int v
, int w
)
{
edge
[++cnt
].to
= v
;
edge
[cnt
].w
= w
;
edge
[cnt
].next
= head
[u
];
head
[u
] = cnt
;
}
int main()
{
scanf("%d%d", &n
, &m
);
for (int i
= 2; i
<= n
; i
++)
{
dis
[i
] = 0x3f3f3f3f;
}
for (int i
= 1; i
<= m
; i
++)
{
int u
, v
, w
;
scanf("%d%d%d", &u
, &v
, &w
);
add(u
, v
, w
);
add(v
, u
, w
);
}
int now
= 1, tot
= 0, sum
= 0;
while (tot
< n
)
{
vis
[now
] = 1;
int MIN
= 0x3f3f3f3f;
for (int i
= 1; i
<= n
; i
++)
{
if (!vis
[i
] && dis
[i
] < MIN
)
{
MIN
= dis
[i
];
now
= i
;
}
}
tot
++;
sum
+= dis
[now
];
ans
= max(dis
[now
], ans
);
for (int i
= head
[now
]; i
; i
= edge
[i
].next
)
{
if (!vis
[edge
[i
].to
] && dis
[edge
[i
].to
] > edge
[i
].w
)
{
dis
[edge
[i
].to
] = edge
[i
].w
;
}
}
}
printf("%d %d", n
- 1, ans
);
return 0;
}
