当前位置:编程学习 > C/C++ >>

MST(prim)+树形dp-hdu-4756-Install Air Conditioning

题目意思:

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

解题思路:

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

PS:

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

代码:

[cpp] view plaincopy
#include<iostream>  
#include<cmath>  
#include<cstdio>  
#include<cstdlib>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<vector>  
#include<map>  
#include<set>  
#include<stack>  
#include<list>  
#include<queue>  
#include<ctime>  
#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,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<n;i++)  
    {  
        dd[i]=dis[0][i];  
        pre[i]=0;  
    }  
    for(int i=1;i<n;i++) //n-1条边  
    {  
        double mi=INF;  
        int re;  
  
        for(int j=0;j<n;j++)  
        {  
            if(!vis[j]&&dd[j]<mi)  
            {  
                mi=dd[j];  
                re=j;  
            }  
        }  
        vis[re]=true;  
        sum+=mi;  
        add(pre[re],re);  
        add(re,pre[re]);  
  
        for(int i=0;i<n;i++)  
        {  
            if(!vis[i]&&dis[re][i]<dd[i])  
            {  
                dd[i]=dis[re][i];  
                pre[i]=re; //更新到集合的距离  
            }  
        }  
    }  
  
}  
  
double dfs(int ro,int fa,int cur,int dep) //表示以cur作为当前子树根中所有子树节点到总根ro的最短距离  
{  
    struct EE * p=head[cur];  
    double mi=INF;  
  
    if(dep!=1) //不为树根的儿子  
        mi=dis[cur][ro];  
    while(p)  
    {  
        int v=p->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<n;i++)  
            scanf("%lf%lf",&pp[i].x,&pp[i].y);  
  
        for(int i=0;i<n;i++)  
        {  
            dis[i][i]=0;  
            for(int j=i+1;j<n;j++)  
            {  
                dis[i][j]=dis[j][i]=Dis(i,j);  
                //edge[nn].a=i,edge[nn].b=j,edge[nn].c=dis[i][j];  
            }  
        }  
        //printf("%d %d\n",nn,m);  
        memset(hav,false,sizeof(hav));  
        memset(head,NULL,sizeof(head));  
        prim();  
        for(int i=0;i<n;i++)  
            for(int j=i+1;j<n;j++)  
                dp[i][j]=dp[j][i]=INF;  
        for(int i=0;i<n;i++)  //以每个点最为树根,对每条边更新n次  
        {  
            dfs(i,i,i,0);  
//            for(int i=0;i<n;i++)  
//                for(int j=i+1;j<n;j++)  
//                {  
//                    printf("i:%d j:%d %lf\n",i,j,dp[i][j]);  
//                }  
            //system("pause");  
        }  
  
        ans=sum;  
        //printf("%lf\n",sum);  
//        for(int i=1;i<n;i++)  
//            for(int j=i+1;j<n;j++)  
//                if(hav[i][j])  
//                    ans=max(ans,sum-dis[i][j]+dp[i][j]);  
        dfs2(0,0);  
        printf("%.2f\n",ans*co);  
    }  
   return 0;  
}  

 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,