pku 3164 最小树形图.txt

ACM资料大集合

#include <stdio.h>
#include <string.h>
#include <math.h>

//PKU 3164 最小树形图
const int MAXV=101,MAXE=10001;
const double MAXDOUBLE=1e20;
double gh[MAXV][MAXV],//原始有向图,顶点从1开始编号
     mincost[MAXV],ans;
int prev[MAXV],stack[MAXV],id[MAXV],mark[MAXV],numv,nume,cnt,top,sta,
     x[MAXV],y[MAXV];//顶点的x,y坐标
bool scaned[MAXV];
void Combine() {
     int i,j,now,x;
     double t;
     now=stack[sta];
     for (i=sta;i<top;i++) 
	 {
         x=stack[i];
         ans+=mincost[x];
         id[x]=now;
         for (j=1;j<=numv;j++) 
		 {
             if (gh[j][x]!=-1) 
			 {
                 t=gh[j][x]-mincost[x];
                 if (t<gh[j][now] || gh[j][now]==-1) 
					 gh[j][now]=t;
             }
             if ((gh[x][j]!=-1 && gh[x][j]<gh[now][j]) || gh[now][j]==-1) 
				 gh[now][j]=gh[x][j];
         }
     }
     for (i=2;i<=numv;i++) 
		 if (id[i]==i) prev[i]=id[prev[i]];
     mincost[now]=MAXDOUBLE;
     for (i=1;i<=numv;i++) 
		 if (i!=now && id[i]==i && gh[i][now]!=-1 && gh[i][now]<mincost[now])
			 mincost[now]=gh[i][now],prev[now]=i;
}
bool Find_Circle() {
     int i,temp,mark[MAXV];
     memset(scaned,0,sizeof(scaned));
     for (i=numv;i>1;i--) {
         if (id[i]!=i || scaned[i]) continue;
         memset(mark,0,sizeof(mark));
         top=1;
         temp=i;
         while (temp!=1 && !mark[temp] && !scaned[temp]) 
		 {
             scaned[temp]=1;
             mark[temp]=top;
             stack[top++]=temp;
             temp=prev[temp];
         }
         if (mark[temp]) 
		 {
             sta=mark[temp];
             return 1;
         }
     }
     return 0;
}
void DFS(int v) 
{
     cnt++;
     scaned[v]=1;
     for (int i=1;i<=numv;i++) 
		 if (!scaned[i] && gh[v][i]!=-1) DFS(i);
}
void Minimum_Arborescence () 
{
     while (Find_Circle()) Combine();
     for (int i=2;i<=numv;i++) if (i==id[i]) ans+=mincost[i];
}
int main () 
{
     int i,j,v1,v2;
     while (scanf("%d%d",&numv,&nume)!=EOF) 
	 {
         for (i=1;i<=numv;i++) for (j=1;j<=numv;j++) gh[i][j]=-1;
         memset(scaned,0,sizeof(scaned));
         for (i=1;i<=numv;i++) scanf("%d%d",&x[i],&y[i]);
         for (i=0;i<nume;i++) 
		 {
             scanf("%d%d",&v1,&v2);
             gh[v1][v2]=sqrt((x[v1]-x[v2])*(x[v1]-x[v2])+(y[v1]-y[v2])*(y[v1]-y[v2]));
         }
         cnt=0;
         DFS(1);
         if (cnt<numv) printf("poor snoopy\n");//最小树形图不存在
         else 
		 {
             id[1]=1;
             for (i=2;i<=numv;i++)
			 {
                 id[i]=i;
                 mincost[i]=MAXDOUBLE;
                 for (j=1;j<=numv;j++) 
					 if(i!=j && gh[j][i]!=-1 && gh[j][i]<mincost[i])
						 mincost[i]=gh[j][i],prev[i]=j;
             }
             ans=0;
             Minimum_Arborescence();
             printf("%.2lf\n",ans);//答案保留两位小数
         }
     }
     return 0;
}