hdu4009

/*
분석:
    최소 트 리 그래프.
    이것 은 이 양식 에 따라 두 드 린 것 이다.
http://www.notonlysuccess.com/index.php/mst/#more-315
                                                 2013-04-26
*/
#include"iostream"
#include"cstdio"
#include"cmath"
#include"cstring"
using namespace std;
const int N=1010;
const int inf=INT_MAX;

int n,X,Y,Z,root;
int id[N],pre[N],in[N],vis[N];
struct node{
	int x,y,z;
}E[N];
struct Edge{
	int f,t,cost;
}edge[N*N];
int tot;
void add(int a,int b,int c){
	edge[tot].f=a;edge[tot].t=b;edge[tot++].cost=c;
}

void build_map()
{
	int i,t,temp,b;
	tot=0;
	for(i=1;i<=n;i++)
	{
		add(0,i,X*E[i].z);
		scanf("%d",&t);
		while(t--)
		{
			scanf("%d",&b);
			if(b==i)	continue;
			temp=abs(E[i].x-E[b].x)+abs(E[i].y-E[b].y)+abs(E[i].z-E[b].z);
			temp*=Y;
			if(E[b].z>E[i].z)	temp+=Z;
			add(i,b,temp);
		}
	}
}

int solve()
{
	int i,u,v,cnt,ans=0,nv=n+1;
	while(1)
	{
		//   node      
		for(i=0;i<nv;i++)	{in[i]=inf;id[i]=-1;vis[i]=-1;}
		for(i=0;i<tot;i++)
		{
			u=edge[i].f;
			v=edge[i].t;
			if(edge[i].cost>=in[v] || u==v)	continue;
			in[v]=edge[i].cost;
			pre[v]=u;
		}
		in[root]=0;
		pre[root]=root;
		//       &&   ans(      ,       ,        。。)
		for(i=0;i<nv;i++)
		{
			ans+=in[i];
			if(in[i]==inf)	return -1;
		}
		//    
		cnt=0;
		for(i=0;i<nv;i++)
		{
			v=i;
			while(vis[v]==-1)
			{
				vis[v]=i;
				v=pre[v];
			}
			if(vis[v]!=i || v==root)	continue;
			for(u=pre[v];u!=v;u=pre[u])	id[u]=cnt;
			id[v]=cnt++;
		}
		if(!cnt)	break;
		for(i=0;i<nv;i++)	if(id[i]==-1)	id[i]=cnt++;
		//   
		for(i=0;i<tot;i++)
		{
			u=edge[i].f;
			v=edge[i].t;
			edge[i].f=id[u];
			edge[i].t=id[v];
			edge[i].cost-=in[v];
		}
		//next
		nv=cnt;
		root=id[root];
	}
	return ans;
}
int main()
{
	int i;
	while(scanf("%d%d%d%d",&n,&X,&Y,&Z),n||X||Y||Z)
	{
		for(i=1;i<=n;i++)	scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].z);
		build_map();
		root=0;
		printf("%d
",solve()); } return 0; }

좋은 웹페이지 즐겨찾기