前一篇提到只需要记录入边就能够实现最小树形图,于是写了一下……
写的其实挺顺利的……不过在算距离的时候把两个点搞反了- -于是悲剧了半天……
| 整体来说代码还是不错,速度也快了点,测试了一下程序跑了1406ms,但是只处理输入,然后直接输出0的程序也跑了1312毫秒,也就是说程序实际上跑了100ms不到的时间,很不错- - |
贴代码……
//最小树形图邻接表
//只记录入边,不记录出边
#include <cstdio>
#include <cstring>
#include <vector>
//include <iostream>
using namespace std;
struct CNode
{
int u;
double l;
CNode(int u, double l){
this->u = u;
this->l = l;
}
};
const int MAXN = 1010;
const double inf = 1e20;
int n, X, Y, Z, m;
vector<CNode> a[MAXN*2];
int pre[MAXN*2], flag[MAXN*2], merge[MAXN*2];
double len[MAXN*2];
double tmpList[MAXN*2];
//若 找到环,返回环第一个点的编号,不然返回-1
int dfs(int u)
{
if(u < 0 || flag[u] < 0)
return -1;
if(flag[u] > 0)
return u;
flag[u] = 1;
int ret = dfs(pre[u]);
flag[u] = -1;
return ret;
}
double ZhuLiu(int root)
{
//判断部分省略,因为必定有解
double ans = 0;
int nn = n;
for(int i = 0; i<2*n; ++i){
merge[i] = i;
pre[i] = -1;
len[i] = inf;
}
for (int v = 0; v < nn; ++v) {
for (vector<CNode>::iterator i = a[v].begin(); i != a[v].end(); ++i) {
if (pre[v] == -1 || len[v] > i->l) {
pre[v] = i->u;
len[v] = i->l;
}
}
}
while(true){
pre[root] = -1;
//找环
bool NoLoop = true;
for(int i = 0; i<nn; ++i)
flag[i] = 0;
for(int i = 0; i<nn; ++i){
if(merge[i] != i)
continue;
int t = dfs(i);
if(t < 0)
continue;
NoLoop = false;
int now = t;
do{
merge[now] = nn;
ans += len[now];
now = pre[now];
}while(now != t);
for(int i = 0; i<nn; ++i){
tmpList[i] = inf;
}
a[nn].clear();
pre[nn] = -1;
len[nn] = inf;
do{
for(vector<CNode>::iterator i = a[now].begin(); i!=a[now].end(); ++i){
int u = i->u;
double l = i->l;
while(merge[u] != u)
u = merge[u];
if(merge[u] == nn)
continue;
l -= len[now];
if(len[nn] > l){
len[nn] = l;
pre[nn] = u;
}
if(tmpList[u] > l)
tmpList[u] = l;
}
now = pre[now];
}while(now != t);
for(int i = 0; i<nn; ++i){
if(tmpList[i] < inf)
a[nn].push_back(CNode(i, tmpList[i]));
}
for(int i = 0; i<nn; ++i){
if(i != root && merge[pre[i]] == nn)
pre[i] = nn;
}
// for(int i = 0; i<nn; ++i){
// if(i == root)
// continue;
// while(merge[pre[i]] != pre[i])
// pre[i] = merge[pre[i]];
// }
nn++;
}
if(NoLoop){
double aa = ans;
for(int i = 0; i<nn; ++i)
if(merge[i] == i && i != root)
ans += len[i];
// for(int i = 0;i<nn; ++i)
// if(merge[i] == i)
// printf("%d->%d %.0f\n", pre[i], i, len[i]);
// printf("sum is %.0f\n", ans-aa);
return ans;
}
}
}
int abs(int k)
{
return k<0?-k:k;
}
int x[MAXN], y[MAXN], z[MAXN];
int GetDis(int u, int v)
{
if(z[u] >= z[v])
return (abs(x[u]-x[v])+abs(y[u]-y[v])+abs(z[u]-z[v]))*Y;
else
return (abs(x[u]-x[v])+abs(y[u]-y[v])+abs(z[u]-z[v]))*Y+Z;
}
bool Solve()
{
scanf("%d%d%d%d", &n, &X, &Y, &Z);
if(n == 0)
return false;
for(int i = 0; i<=n; ++i){
a[i].clear();
}
for(int i = 1; i<=n; ++i)
scanf("%d%d%d", &x[i], &y[i], &z[i]);
for(int i = 1; i<=n; ++i){
int k;
scanf("%d", &k);
int v;
for(int j = 0; j<k; ++j){
scanf("%d", &v);
if(i == v)
continue;
a[v].push_back(CNode(i, GetDis(i, v)));
}
}
for(int i = 1; i<=n; ++i){
a[i].push_back(CNode(0, X*z[i]));
}
n++;
printf("%.0f\n", ZhuLiu(0));
return true;
}
int main(int argc, char** argv)
{
// freopen("in.txt", "r", stdin);
while(Solve());
return 0;
}