很裸的一道最小瓶颈路的模板题,先求最小生成树,然后在求点对点的最小瓶颈路
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N = 210; const double INF = 1000000; int n, p[N]; double x[N], y[N], map[N][N], f[N][N], s1; bool mark[N]; void prim() { bool vis[N]; memset(vis, 0, sizeof(vis)); double d[N], mi; for ( int i = 1; i <= n; ++i ) d[i] = INF, p[i] = -1; d[1] = 0.0, s1 = 0; int v; for ( int u = 0; u < n; ++u ) { mi = INF; for ( int i = 1; i <= n; ++i ) if ( !vis[i] && d[i] < mi ) mi = d[i], v = i; vis[v] = true; s1 += mi; for ( int i = 1; i <= n; ++i ) if ( !vis[i] && d[i] > map[v][i] ) d[i] = map[v][i], p[i] = v; } //printf("%lf\n", s1); } void dfs( int v ) { for ( int u = 1; u <= n; ++u ) { if ( !mark[u] && p[u] == v ) { mark[u] = true; for ( int x = 1; x <= n; ++x ) if ( mark[x] && x != u ) f[x][u] = f[u][x] = max( f[x][v], map[u][v] ); dfs(u); } } } int main() { int icase = 1; while ( scanf("%d", &n), n) { for ( int i = 1; i <= n; ++i ) scanf("%lf%lf", &x[i], &y[i]); for ( int i = 1; i <= n; ++i ) for ( int j = i+1; j <= n; ++j ) map[i][j] = map[j][i] = sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j])); prim(); memset(mark, 0, sizeof(mark)); for ( int i = 1; i <= n; ++i ) for ( int j = 1; j <= n; ++j ) f[i][j] = 0.0; mark[1] = true; dfs( 1 ); //for ( int i = 1; i <= n; printf("\n"), ++i ) for ( int j = 1; j <= n; ++j ) printf("%lf ", f[i][j]); printf("Scenario #%d\n", icase++); printf("Frog Distance = %.3lf\n\n", f[1][2]); } }