首先为除根之外的每个点选定一条入边,这条入边一定要是所有入边中最小的
除第一个点外,在另外点上找是否有向环的起点
如果有,先把环上边权加到res中,标记环上的点,再调整有向环的起点上的入边
调整有向环上其它点的入边和出边(取环上点到非环上点的最小值为环到k的值)(把环上点缩到i上)
如果找全就跳出返回最小树形图的值
调整的时候入边要减掉in[u];
//pku 3164
#include<stdio.h>
#include<string.h>
#include<math.h>
#define N 110
#define M 1<<27
struct P
{
double x, y;
}p[N];
double g[N][N],ans;
int visit[N],n,m,pre[N],circle[N],del[N];
double minn(double a, double b)
{
return a<b?a:b;
}
double dis(P a, P b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void dfs(int x)
{
for(int i=1; i<=n; i++)
if(!visit[i] && g[x][i]!=M){
visit[i]=1;
dfs(i);
}
}
int exist(){//判连通
int i,root=1;
memset(visit, 0, sizeof(visit));
visit[root]=true;
dfs(root);
for(i=1; i<=n; i++)
if(!visit[i])
return 0;
return 1;
}
void S_Tree()
{
int i,j,k,in,mark;
memset(del, 0, sizeof(del));
while(1){
for(i=2; i<=n; i++)
if(!del[i]){//找每个点的最小入度
pre[i]=i;
g[i][i]=M;
for(j=1; j<=n; j++)
if(!del[j] && g[j][i]<g[pre[i]][i]){
pre[i]=j;
}
}
for(i=2; i<=n; i++)
if(!del[i]){
memset(visit, 0, sizeof(visit));
mark=i;
while(!visit[mark] && mark!=1){//找环
visit[mark]=1;
mark=pre[mark];
}
if(mark==1) //若无环,则必会找到根节点,continue;
continue;
i=mark; //否则就有环
ans+=g[pre[i]][i];
for(j=pre[i]; j!=i; j=pre[j]){
ans+=g[pre[j]][j]; //加环上的权值
del[j]=1;
}
for(j=1; j<=n; j++) //处理外界点与环上点的权值
if(!del[j]){
if(g[j][i]!=M)
g[j][i]-=g[pre[i]][i];
}
for(j=pre[i]; j!=i; j=pre[j]){ //处理环上点与外界点的权值
for(k=1; k<=n; k++)
if(!del[k]){
g[i][k]=minn(g[i][k], g[j][k]);
if(g[k][j]!=M){
g[k][i]=minn(g[k][i], g[k][j]-g[pre[j]][j]);
}
}
}
break;//做完一次缩点工作就跳出,继续生成新的图
}
if(i>n){
for(j=2; j<=n; j++)
if(!del[j]){
ans+=g[pre[j]][j];
}
break;
}
}
}
int main()
{
int i,j,k;
while(scanf("%d %d",&n, &m)!=EOF){
ans=0;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
g[i][j]=M;
for(i=1; i<=n; i++)
scanf("%lf %lf", &p[i].x, &p[i].y);
for(i=0; i<m; i++){
scanf("%d %d", &j, &k);
g[j][k]=dis(p[j], p[k]);
}
i=exist();
if(!exist())
printf("poor snoopy\n");
else{
S_Tree();
printf("%.2lf\n", ans);
}
}
return 0;
}