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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.