hdu 4081 最小生成树+树形dp

思路:直接先求一下最小生成树,然后用树形dp来求最优值。也就是两遍dfs。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define Maxn 2010
using namespace std;
struct Edge{
int u,v;
double c;
int operator <(const Edge &temp) const
{
return c<temp.c;
}
}p[];
struct PP{
int u,v,next;
double val;
}edge[Maxn*];
struct Point{
double x,y;
}city[Maxn];
int set[Maxn],e,vi[],num[Maxn],head[Maxn],road[Maxn],Max[Maxn],lMax[Maxn];
double ans,S;
int find(int x)
{
if(x!=set[x])
set[x]=find(set[x]);
return set[x];
}
int merg(int a,int b)
{
int x,y;
x=find(a);
y=find(b);
if(x==y)
return ;
set[x]=y;
return ;
}
void add(int u,int v,double val)
{
edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].next=head[u],head[u]=e++;
edge[e].u=v,edge[e].v=u,edge[e].val=val,edge[e].next=head[v],head[v]=e++;
memset(Max,,sizeof(Max));
}
double DIS(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void init()
{
for(int i=;i<Maxn;i++)
set[i]=i,num[i]=;
memset(head,-,sizeof(head));
memset(vi,,sizeof(vi));
memset(road,,sizeof(road));
e=;
}
void dfs(int u)
{
int i,v;
vi[u]=;
Max[u]=lMax[u]=num[u];
for(i=head[u];i!=-;i=edge[i].next){
v=edge[i].v;
if(vi[v]) continue;
dfs(v);
if(Max[v]>Max[u]){
lMax[u]=Max[u];
Max[u]=Max[v];
road[u]=v;
}
else if(Max[v]>lMax[u]){
lMax[u]=Max[v];
}
}
}
void predfs(int u,int sum)
{
int i,v;
vi[u]=;
double a,b;
for(i=head[u];i!=-;i=edge[i].next){
v=edge[i].v;
if(vi[v]) continue;
if(road[u]==v) a=max(lMax[u],sum);
else a=max(sum,Max[u]);
a+=Max[v];
b=S-edge[i].val;
if(a/b>ans){
ans=a/b;
}
if(road[u]==v) predfs(v,max(lMax[u],sum));
else predfs(v,max(Max[u],sum));
}
}
int main()
{
int t,n,m,i,j,x,y,c;
scanf("%d",&t);
while(t--)
{
init();
scanf("%d",&n);
for(i=;i<=n;i++)
scanf("%lf%lf%d",&city[i].x,&city[i].y,&num[i]);
int cnt=;
for(i=;i<=n;i++){
for(j=i+;j<=n;j++){
p[++cnt].u=i,p[cnt].v=j,p[cnt].c=DIS(city[i],city[j]);
}
}
sort(p+,p++cnt);
int cc=;
double temp=;
int lis[Maxn];
for(i=;i<=cnt;i++){
if(merg(p[i].u,p[i].v)){
temp+=p[i].c;
lis[++cc]=i;
}
if(cc==n-)
break;
}
for(i=;i<=cc;i++){
add(p[lis[i]].u,p[lis[i]].v,p[lis[i]].c);
}
S=temp;
ans=;
dfs();
memset(vi,,sizeof(vi));
predfs(,);
printf("%.2lf\n",ans);
}
return ;
}
上一篇:跟我一起学WPF(1):WPF的UI设计语言——XAML


下一篇:DNS,TCP,IP,HTTP,socket,Servlet概念整理