需要注意,因为增加一个零点,最后总点数要加1;
此模板的边和点都从0开始计数
废话一句,厚积方能薄发啊。
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;
}