这道题求最小生树中第k小的边,很多人用的是kruskal算法,但是由于边很多的,其实我觉得正解应该是prim比较省时
那么如果用prim我们怎么去求,那就要明确去一个概念,在实现prim的时候,有一个用于记录的数组,它存放第i个节点到集合(已经被选为最小生成树的点的集合)的最小边的权值,那么不管这个i节点和集合中哪一个点相连,当函数结束的时候,它就是表示i节点到它应当连接的那个节点的边的权值,那以此类推,d数组就是存放了最小生成树中的边的权值。
注意,d[1]这个起始点为0,因为1前面没有边了。
那么代码如下:
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; int s, p; bool vis[550]; double map[550][550], d[550], x[550], y[550]; double dis( double a1, double a2, double b1, double b2 ) { return sqrt( (a1-a2)*(a1-a2) + ( b1-b2)*(b1-b2) ); } void prim() { double m; int mark; for ( int k = 1; k < p; ++k ) { m=100000000; for ( int i = 1; i <= p; ++i ) if ( !vis[i] && m > d[i] ) m = d[i], mark = i; vis[mark] = true; for ( int i = 1; i <= p; ++i ) if ( !vis[i] && map[mark][i] < d[i] ) d[i] = map[mark][i]; } } bool cmp( double a, double b ) { return a < b; } int main() { int icase; scanf("%d", &icase); while ( icase--) { scanf("%d%d", &s, &p); for ( int i = 1; i <= p; ++i ) scanf("%lf%lf", &x[i], &y[i]); for ( int i = 1; i <= p; ++i ) for ( int j = 1; j <= p; ++j ) map[i][j] = dis(x[i], x[j], y[i], y[j]); memset( vis, 0, sizeof(vis) ); for ( int i = 1; i <= p; ++i ) d[i] = map[1][i]; vis[1] = true; prim(); sort(d + 1, d + 1 + p ); printf("%.2lf\n", d[p-s+1]); } }