UVa 534 Frogger(최소 병목 지점)

매우 누드적인 최소 병목로의 템플릿 문제, 먼저 최소 생성 나무를 구한 다음에 점대점의 최소 병목로를 구한다.
코드는 다음과 같습니다.
#include 
#include 
#include 
#include 
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
", 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("
"), ++i ) for ( int j = 1; j <= n; ++j ) printf("%lf ", f[i][j]); printf("Scenario #%d
", icase++); printf("Frog Distance = %.3lf

", f[1][2]); } }

좋은 웹페이지 즐겨찾기