hdu 4009最小树形图邻接表版

时间:2022-11-13 16:02:29

需要注意,因为增加一个零点,最后总点数要加1;

此模板的边和点都从0开始计数

废话一句,厚积方能薄发啊。

hdu 4009最小树形图邻接表版hdu 4009最小树形图邻接表版View Code
#include<stdio.h>
#include
<stdlib.h>
#include
<math.h>
#include
<string.h>
#define maxn 1005
const int inf =1000000000;
struct Edge
{
int s,t;
int cost;
}edge[maxn
*maxn];
struct node{
int x,y,z;
}a[maxn];
int E,nv,ne;
int pre[maxn],Id[maxn],vis[maxn];
int in[maxn];
//最小树形图邻接表版本,三步走,找最小入弧,找有向环,缩环为点
int Directed_MST(int root)//点和边都是从0开始的
{//返回-1 为无最小树形图 返回为最小树形图值
int i,s,t;
nv
++;
int ret = 0;
while(1)
{
//find the smallest in-arc
for(i=0;i<nv;i++) in[i] = inf,Id[i]=-1,vis[i]=-1;
for(i = 0;i < ne;i++)
{
s
= edge[i].s;
t
= edge[i].t;
if(edge[i].cost>=in[t] || s == t)continue;
pre[t]
= s;
in[t] = edge[i].cost;

}
in[root] = 0; pre[root]=root;
for(i = 0;i < nv;i++)
{
ret
+= in[i];
if(in[i] == inf)
return -1;
//there are some nodes other than root with no in-arc connected to it
}
//find the dir circle
int Idx = 0;
for(i = 0;i < nv;i++)if(vis[i]==-1)
{
t
= i;
while(vis[t]==-1)
{
vis[t]
= i;
t
= pre[t];
}
if(vis[t]!=i||t==root)continue;
for(int s = pre[t]; s != t;s = pre[s])
Id[s]
= Idx;
Id[t]
= Idx++;
}
if(Idx == 0) break;//no circle
for(i = 0;i < nv;i++) if(Id[i] == -1)
Id[i]
= Idx++;
//compress the nodes;
for(i = 0;i < ne;i++)
{
int v = edge[i].t;
edge[i].s
= Id[edge[i].s];
edge[i].t
= Id[edge[i].t];
edge[i].cost
-= in[v];
}
nv
= Idx;
root
= Id[root];
}
return ret;
}
void add(int s,int t,int cost)
{
edge[ne].s
=s;
edge[ne].t
=t;
edge[ne
++].cost=cost;
}
int dist(int i,int j)
{
return abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)+abs(a[i].z-a[j].z);
}
int main()
{
int i,j,x,y,z,k,temp;
while(scanf("%d%d%d%d",&nv,&x,&y,&z)!=EOF)
{
ne
=0;
if(nv==0) break;
for(i=1;i<=nv;i++)
{
scanf(
"%d%d%d",&a[i].x,&a[i].y,&a[i].z);
add(
0,i,a[i].z*x);
}
for(i=1;i<=nv;i++)
{
scanf(
"%d",&k);
for(j=0;j<k;j++)
{
scanf(
"%d",&temp);
if(temp==i) continue;
if(a[i].z>=a[temp].z)
add(i,temp,dist(i,temp)
*y);
else add(i,temp,dist(i,temp)*y+z);
}
}
printf(
"%d\n",Directed_MST(0));
}
return 0;
}