#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define INF 99999999
#define min( a, b ) ( (a)< (b)?(a): (b) )
int x[110], y[110], father[110];
double map[110][110], ans;
bool visite[110], circle[110];
int n, m, root;
void dfs( int t )
{
visite[t]= true;
for( int i= 1; i<= n; ++i )
if( !visite[i] && map[t][i]!= INF )
dfs( i );
}
bool isok()
{
memset( visite, false, sizeof(visite) );
dfs( root );
for( int i= 1; i<= n; ++i )
if( !visite[i] ) return false;
return true;
}
double dist( int i, int j )
{
return sqrt( (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) );
}
int exist_circle()
{
root= 1; father[root]= root;
for( int i= 1; i<= n; ++i )
if( !circle[i] && i!= root )
{
father[i]= i; map[i][i]= INF;
for( int j= 1; j<= n; ++j )
if( !circle[j] && map[j][i]< map[father[i]][i] )
father[i]= j;
}
int i;
for( i= 1; i<= n; ++i )
{
if( circle[i] ) continue;
memset( visite, false, sizeof(visite) );
int j= i;
while( !visite[j] ) { visite[j]= true; j= father[j]; }
if( j== root ) continue;
return j;
}
return -1;
}
void update( int t )
{
ans+= map[father[t]][t];
for( int i= father[t]; i!= t; i= father[i] )
{
ans+= map[father[i]][i];
circle[i]= true;
}
for( int i= 1; i<= n; ++i )
if( !circle[i] && map[i][t]!= INF )
map[i][t]-= map[father[t]][t];
for( int j= father[t]; j!= t; j= father[j] )
for( int i= 1; i<= n; ++i )
{
if( circle[i] ) continue;
if( map[i][j]!= INF )
map[i][t]= min( map[i][t], map[i][j]- map[father[j]][j] );
map[t][i]= min( map[j][i], map[t][i] );
}
}
void solve()
{
memset( circle, false, sizeof(circle) );
int j;
while( ( j= exist_circle() )!= -1 ) update( j );
for( j= 1; j<= n; ++j )
if( j!= root && !circle[j] )
ans+= map[father[j]][j];
printf("%.2lf\n", ans );
}
int main()
{
while( scanf("%d%d",&n,&m)!= EOF )
{
for( int i= 0; i<= n; ++i )
for( int j= 0; j<= n; ++j )
map[i][j]= INF;
for( int i= 1; i<= n; ++i )
scanf("%d%d",&x[i], &y[i] );
for( int i= 0; i< m; ++i )
{
int a, b;
scanf("%d%d",&a,&b);
map[a][b]= dist( a, b );
}
root= 1; ans= 0;
if( !isok() ) puts("poor snoopy");
else solve();
}
return 0;
}
posted on 2009-02-19 22:01
Darren 閱讀(203)
評(píng)論(0) 編輯 收藏 引用