HDoj 4009 Transfer water【受動点最小樹形図】【好題】
3816 ワード
テーマ:hdoj 4009 Transfer water
题目:题目は少し长くて、ある村があって、n戸の家が水を使うと言って、彼らが加えた位置は3次元の座標で表して(x,y,z)、彼らは2つの选択があります:
1:自分で井戸を掘って、費用はz*cost_x
2:他人の家から水道管を受け取ってきて、距離*cost_になるy、引く場所が今の場所より低ければ、ポンプを1つ買ってcost_z.
距離アルゴリズム|x 2‐x 1|+|y 2‐y 1|+|z 2‐z 1|.
そしてすべての人に役立つ水の最小費用を求め、
解析:最小生成ツリーを求めるテーマであることが分かったが、キーは2つある.
1:源点が多く、井戸を自作しているところはすべて源点です.
2:図は有向図で、これは明らかに最小の木の形の図を思い付きます
では、最初の点を処理するのは簡単です.ソース点Sを追加して、sと各点に縁を結んで、井戸を掘るのにかかる距離を置いて、この点で最小の木の図でokになります.
ACコード:
题目:题目は少し长くて、ある村があって、n戸の家が水を使うと言って、彼らが加えた位置は3次元の座標で表して(x,y,z)、彼らは2つの选択があります:
1:自分で井戸を掘って、費用はz*cost_x
2:他人の家から水道管を受け取ってきて、距離*cost_になるy、引く場所が今の場所より低ければ、ポンプを1つ買ってcost_z.
距離アルゴリズム|x 2‐x 1|+|y 2‐y 1|+|z 2‐z 1|.
そしてすべての人に役立つ水の最小費用を求め、
解析:最小生成ツリーを求めるテーマであることが分かったが、キーは2つある.
1:源点が多く、井戸を自作しているところはすべて源点です.
2:図は有向図で、これは明らかに最小の木の形の図を思い付きます
では、最初の点を処理するのは簡単です.ソース点Sを追加して、sと各点に縁を結んで、井戸を掘るのにかかる距離を置いて、この点で最小の木の図でokになります.
ACコード:
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1100;
const int inf = 0x3f3f3f3f;
int n,m;
struct Node
{
int from,to,dis;
};
vector<Node> e;
int ha[N],vis[N],father[N],in[N];
int Minroot;
int zhuliu(int root)
{
int ans = 0;
while(true)
{
for(int i=0;i<n;i++)
in[i] = inf;
memset(father,-1,sizeof(father));
for(int i=0; i<e.size(); i++) //
{
int to = e[i].to;
if(e[i].dis<in[to] && e[i].from!=e[i].to)
{
in[to] = e[i].dis;
father[to] = e[i].from;
// if(e[i].from == root) //
// Minroot = i;
}
}
for(int i=0;i<n;i++)
{//printf("%d ",in[i]);
if(i!=root && in[i]==inf)
return -1;
}
int cnt = 0;
in[root] = 0;
memset(ha,-1,sizeof(ha));
memset(vis,-1,sizeof(vis));
for(int i=0;i<n;i++) //
{
ans += in[i];
int v = i;
while(v!=root && ha[v]==-1 && vis[v]!=i)
{
vis[v] = i;
v = father[v];
}
if(v!=root && ha[v]==-1)
{
for(int j = father[v];j != v;j=father[j])
{
ha[j] = cnt;
}
ha[v] = cnt++;
}
}
if(cnt == 0) //
break;
for(int i=0;i<n;i++)
if(ha[i]==-1)
ha[i]=cnt++;
for(int i = 0; i< e.size();i++)
{
int tmp = e[i].to;
e[i].from = ha[e[i].from];
e[i].to = ha[e[i].to];
if(e[i].from != e[i].to)
e[i].dis -= in[tmp];
}
n = cnt;
root = ha[root];
}
return ans;
}
struct Tree
{
int x,y,z;
};
Tree p[N];
int dis(Tree a,Tree b)
{
return abs(a.x-b.x)+abs(a.y-b.y)+abs(a.z-b.z);
}
int main()
{
//freopen("Input.txt","r",stdin);
int x,y,z;
while(~scanf("%d%d%d%d",&n,&x,&y,&z) && n+x+y+z)
{
for(int i=0;i<n;i++)
{
scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
}
for(int i=0;i<n;i++)
{
int k,x;
scanf("%d",&k);
while(k--)
{
scanf("%d",&x);
x--;
if(x==i)
continue;
int tmp = dis(p[i],p[x])*y;
if(p[i].z<p[x].z)
tmp+=z;
e.push_back((Node){i,x,tmp});
}
}
n++;
for(int i=0;i<n-1;i++)
{
e.push_back((Node){n-1,i,p[i].z*x});
}
// for(int i=0;i<e.size();i++)
// {
// printf("%d %d %d
",e[i].from,e[i].to,e[i].dis);
// }
int ans = zhuliu(n-1);
printf("%d
",ans);
e.clear();
}
return 0;
}