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++ ,