/*调了一下午的最小树形图，昨天刚刚看懂模板。。最小树形图，就是有向图的最小生成树，很神奇==*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define MAXN 1002
#define INF 0x3f3f3f3f
using namespace std;
struct Node{
int x,y,z;
}nodes[MAXN];
struct Edge{
int u,v,w;
}e[MAXN*
MAXN];
int tot;
int dist(
int a,
int b,
int y,
int z){
int res=
0;
res+=abs(nodes[a].x-nodes[b].x)*y+abs(nodes[a].y-nodes[b].y)*y+abs(nodes[a].z-nodes[b].z)*
y;
if(nodes[a].z<
nodes[b].z)
res+=
z;
return res;
}
int pre[MAXN],id[MAXN],visit[MAXN],
in[MAXN];
int zhuliu(
int root,
int n,
int m){
int res=
0,u,v;
while(
1){
for(
int i=
0;i<n;i++
)
in[i]=
INF;
//建立最小弧集E
for(
int i=
0;i<m;i++
)
if(e[i].u!=e[i].v && e[i].w<
in[e[i].v]){
pre[e[i].v]=
e[i].u;
in[e[i].v]=
e[i].w;
}
for(
int i=
0;i<n;i++
)
if(i!=root &&
in[i]==
INF)
return -
1;
//不存在最小树形图
int tn=
0;
memset(id,-
1,
sizeof id);
memset(visit,-
1,
sizeof visit);
in[root]=
0;
for(
int i=
0;i<n;i++){
//找环染色
res+=
in[i];
v=
i;
while(visit[v]!=i && id[v]==-
1 && v!=
root){
visit[v]=
i;
v=
pre[v];
}//找环
if(v!=root && id[v]==-
1){
for(
int u=pre[v];u!=v;u=
pre[u])
id[u]=
tn;
id[v]=tn++
;
}//染色
}
if(tn==
0)
//没有环
break;
for(
int i=
0;i<n;i++)
//给没有环的点染色
if(id[i]==-
1)
id[i]=tn++
;
for(
int i=
0;i<m;){
//
v=
e[i].v;
e[i].u=
id[e[i].u];
e[i].v=
id[e[i].v];
if(e[i].u!=e[i].v)
//如果是在不同的环里
e[i++].w -=
in[v];
else
swap(e[i],e[--
m]);
}
n=tn;
//剩下tn个点
root=
id[root];
}
return res;
}
int main(){
int n,x,y,z,k,v;
while(scanf(
"%d%d%d%d",&n,&x,&y,&z)!=EOF &&
n){
tot=
0;
for(
int i=
1;i<=n;i++
)
scanf("%d%d%d",&nodes[i].x,&nodes[i].y,&
nodes[i].z);
for(
int u=
1;u<=n;u++
){
scanf("%d",&
k);
while(k--
){
scanf("%d",&
v);
e[tot].u=
u;
e[tot].v=
v;
e[tot].w=
dist(u,v,y,z);
tot++
;
}
}
int root=
0;
for(
int i=
1;i<=n;i++
){
e[tot].u=
root;
e[tot].v=
i;
e[tot].w=x*
nodes[i].z;
tot++
;
}
printf("%I64d\n",zhuliu(root,n+
1,tot));
}
return 0;
}
转载于:https://www.cnblogs.com/zsben991126/p/9792120.html
