MST(prim)+树形dp-hdu-4756-Install Air Conditioning - c++编程基础

题目意思：

n-1个宿舍，1个供电站，n个位置每两个位置都有边相连，其中有一条边不能连，求n个位置连通的最小花费的最大值。

解题思路：

和这道题hdu-4126差不多，不过这题不能去掉与供电站相连的边。不同的是这题是一个完全图，求MST时，用kruscal算法的时间复杂度为elge很高会超时，用prim算法复杂度为n^2,所以选用prim算法。

PS：

double类型的不能用memset,置最大，wa了一个多小时。

代码：

[cpp] view plaincopy
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define eps 1e-6  
#define INF 0x3f3f3f3f  
#define PI acos(-1.0)  
#define ll __int64  
#define lson l,m,(rt<<1)  
#define rson m+1,r,(rt<<1)|1  
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;  
  
#define Maxn 1300  
  
struct Po  
{  
    double x,y;  
}pp[Maxn];  
  
double dis[Maxn][Maxn]; //原始距离  
bool hav[Maxn][Maxn],vis[Maxn]; //是否为最小生成树上的边  
int pre[Maxn],;  
double dp[Maxn][Maxn];//dp[i][j]表示为最小生成树上的边，且去掉该边后，包括点i的连通块中的点集A到包括点j的连通块点集B的最小距离。  
int n,m,cnt;  
double sum,ans,dd[Maxn];  
  
  
  
struct EE //构建最小生成树  
{  
    int v;  
    struct EE * next;  
}ee[Maxn<<1],*head[Maxn<<1];  
  
void add(int a,int b)  
{  
    ++cnt;  
    ee[cnt].v=b;  
    ee[cnt].next=head[a];  
    head[a]=&ee[cnt];  
}  
void prim()  
{  
    cnt=0,sum=0;  
    memset(vis,false,sizeof(vis));  
    dd[0]=0;  
    pre[0]=0;  
    vis[0]=true;  
    for(int i=1;i




v;  
        if(v!=fa)  
        {  
            //printf(":%d\n",v);  
            //system("pause");  
            double tt=dfs(ro,cur,v,dep+1);  
            mi=min(mi,tt);  
            dp[cur][v]=dp[v][cur]=min(dp[v][cur],tt);//更新当前边  
  
        }  
        p=p->next;  
    }  
    return mi;  
  
}  
double Dis(int i,int j)  
{  
    return sqrt(pow(pp[i].x-pp[j].x,2.0)+pow(pp[i].y-pp[j].y,2.0));  
}  
void dfs2(int cur,int fa)  
{  
    struct EE * p=head[cur];  
  
    while(p)  
    {  
        int v=p->v;  
        if(v!=fa)  
        {  
            if(fa)  
                ans=max(ans,sum-dis[cur][v]+dp[cur][v]);  
            dfs2(v,cur);  
        }  
        p=p->next;  
    }  
}  
int main()  
{  
   // printf("%d\n",INF);  
    double co;  
    int tt;  
    scanf("%d",&tt);  
    while(tt--)  
    {  
        scanf("%d%lf",&n,&co);  
        for(int i=0;i