hdu 4009 最小树形图

思路:唯一一个值得一提的就是建一个0号根节点,往每个房子建一条边,权值为房子的高度乘以X。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define Maxn 1010
#define Maxm Maxn*Maxn
#define inf 100000000
using namespace std;
int head[Maxn],vi[Maxn],id[Maxn],in[Maxn],pre[Maxn],cnt,X,Y,Z,n,e;
struct Edge{
int u,v,next,val;
}edge[Maxm];
struct Point{
int x,y,z;
}p[Maxn];
void init()
{
memset(head,-,sizeof(head));
e=;
}
void add(int u,int v,int val)
{
edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].next=head[u],head[u]=e++;
}
int Dis(Point a,Point b)
{
return abs(a.x-b.x)+abs(a.y-b.y)+abs(a.z-b.z);
}
int directed_MST(int root,int N,int E)
{
int ans=,i,j,u,v;
while()
{
for(i=;i<N;i++)
in[i]=inf;
for(i=;i<E;i++)
{
u=edge[i].u,v=edge[i].v;
if(in[v]>edge[i].val&&u!=v)
{
pre[v]=u;
in[v]=edge[i].val;
}
}
for(i=;i<N;i++)
{
if(i==root) continue;
if(in[i]==inf) return -;
}
memset(vi,-,sizeof(vi));
memset(id,-,sizeof(id));
cnt=;
in[root]=;
for(i=;i<N;i++)//枚举每个可能是环上的点
{
ans+=in[i];
v=i;
while(vi[v]!=i&&id[v]==-&&v!=root)
{
vi[v]=i;v=pre[v];
}
if(v!=root&&id[v]==-)//如果退出上个循环的条件不是v==root,就是vi[i]==i,即找到了环
{
for(u=pre[v];u!=v;u=pre[u])//对环进行统一标号
id[u]=cnt;
id[v]=cnt++;
}
}
if(cnt==) break;//无环 ,退出
for(i=;i<N;i++) if(id[i]==-) id[i]=cnt++;
for(i=;i<E;i++)//进行缩点,并修改每条边的权值。
{
v=edge[i].v;
edge[i].u=id[edge[i].u];
edge[i].v=id[edge[i].v];
if(edge[i].u!=edge[i].v)
edge[i].val-=in[v];
}
N=cnt;
root=id[root];
}
return ans;
}
int main()
{
int i,j,a,b,c,k;
while(scanf("%d%d%d%d",&n,&X,&Y,&Z),n|X|Y|Z)
{
init();
for(i=;i<=n;i++)
scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
for(i=;i<=n;i++)
{
scanf("%d",&k);
for(j=;j<=k;j++)
{
scanf("%d",&a);
if(a==i) continue;
if(p[a].z>p[i].z)
add(i,a,Dis(p[a],p[i])*Y+Z);
else
add(i,a,Dis(p[a],p[i])*Y);
}
}
for(i=;i<=n;i++)
add(,i,X*p[i].z);
printf("%d\n",directed_MST(,n+,e));
}
return ;
}
上一篇:JS中document对象详解


下一篇:关于css样式line-height的应用