传送门

前前后后调了几个小时,交了$30$发…

原来板子是没错的,但是如果虚根是$0$

那么每次的编号就要从$0$起

对应的$vis$和$id$数组就不能判断是否为$0$

每次更新点数也要变化…

下次绝对不用下标$0$的了…我吐了

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
const int inf = 2e9;
int n,m,root,X,Y,Z,top;
int x[maxn],y[maxn],z[maxn];
int dis(int l,int r)
{return abs(x[l]-x[r])+abs(y[l]-y[r])+abs(z[l]-z[r]);
}
struct edge{int u,v,w;
}a[maxn];
int pre[maxn],inw[maxn],id[maxn],vis[maxn];
int zhuliu(int root,int n)
{int ans=0;while( 1 ){for(int i=1;i<=n;i++)	inw[i]=inf;for(int i=1; i<=top ;i++){int u=a[i].u,v=a[i].v;if( u!=v&&a[i].w<inw[v] )//为每个点找最小入边 inw[v]=a[i].w,pre[v]=u;}for(int i=1;i<=n;i++)//没有入边就无解 if( i!=root&&inw[i]==inf )	return -1;int cnt=0;for(int i=1;i<=n;i++)	vis[i]=id[i]=0;for(int i=1;i<=n;i++){if( i==root )	continue;ans+=inw[i];int v=i;//首先vis[i]!=i是避免重复走环,!id[v]是不能走到之前的环去//v!=root因为root没有入边,可以退出了 while( vis[v]!=i&&v!=root&&!id[v] )vis[v]=i,v=pre[v];if( !id[v]&&v!=root )//没走到根节点,说明有环{id[v]=++cnt;//标记环中的点for(int u=pre[v];u!=v;u=pre[u] )id[u]=cnt;	} }if( cnt==0 )	break;//无环,是最小树形图for(int i=1;i<=n;i++)	if( !id[i] )	id[i]=++cnt;for(int i=1;i<=top;i++){int u=a[i].u,v=a[i].v;a[i].u=id[u],a[i].v=id[v];//缩点if( id[u]!=id[v] )	a[i].w-=inw[v];//修改边权 }root=id[root];n=cnt; }return ans;
}
int main()
{while( scanf("%d%d%d%d",&n,&X,&Y,&Z )!=EOF&&(n+X+Y+Z) ){top = 0;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);for(int j=1;j<=k;j++){int id; scanf("%d",&id);a[++top].u = i, a[top].v = id;if( z[i]>=z[id] )	a[top].w = dis(i,id)*Y;else	a[top].w = dis(i,id)*Y+Z;}}for(int i=1;i<=n;i++)a[++top].u = n+1, a[top].v = i, a[top].w = z[i]*X;int ans = zhuliu(n+1,n+1);cout << ans << endl; }
}