hdu 4081 Qin Shi Huang's National Road System (最小生成树变形 两种解法 1.Prim 2.dfs)(二)

#include   
#include   
#include   
#include   
#define maxn 1005  
#define INF 0x3f3f3f3f  
using namespace std ;  
  
int n,m,cnt,nu,nv,maxp;  
bool vis[maxn];  
int pre[maxn];  
double sum,ans;  
double dist[maxn];  
double city[maxn][maxn],dd[maxn][maxn];  
struct Node  
{  
    int x,y,p;  
}pp[maxn];  
int pt[maxn];  
struct node  
{  
    int v,next;  
}edge[maxn<<1];  
struct Tnode  
{  
    int u,v;  
    double cost;  
}mst[maxn];  
  
void init()  
{  
    int i,j;  
    for(i=1;i<=n;i++)  
    {  
        dist[i]=INF;  
        for(j=1;j<=n;j++)  
        {  
            city[i][j]=INF;  
        }  
    }  
    cnt=0;  
    memset(pt,0,sizeof(pt));  
    memset(vis,0,sizeof(vis));  
}  
double caldist(int k1,int k2)  
{  
    double xx,yy;  
    xx=pp[k1].x-pp[k2].x;  
    yy=pp[k1].y-pp[k2].y;  
    return sqrt(xx*xx+yy*yy);  
}  
void presolve()  
{  
    int i,j;  
    for(i=1;i<=n;i++)  
    {  
        for(j=i+1;j<=n;j++)  
        {  
            city[i][j]=city[j][i]=caldist(i,j);  
        }  
    }  
}  
void addedge(int u,int v)  
{  
    cnt++;  
    edge[cnt].v=v;  
    edge[cnt].next=pt[u];  
    pt[u]=cnt;  
}  
void prim()  
{  
    int i,j,k,sz,now=1;  
    double mi;  
    sum=0;  
    vis[1]=1;  
    dist[1]=0;  
    for(i=1;i