多建一个根,连到每一个点,然后花费是建水井的钱

然后跑一边最小树形图即可,这题必定有解,因为可以从根开始到每一点,可以不用判无解的情况

#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define MIN(a,b) a<b ? a:b using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f3f; struct edge{
int u,v,w;
}e[maxn];
struct pe{
int x,y,z;
}p[N];
int pre[N],in[N],vis[N];
int ans,Hash[N];
int dis(int a,int b)
{
return abs(p[a].x-p[b].x)+abs(p[a].y-p[b].y)+abs(p[a].z-p[b].z);
}
bool dirmst(int root,int nv,int ne)
{
ans=;
while(){
memset(in,inf,sizeof in);
for(int i=;i<ne;i++)
{
int u=e[i].u,v=e[i].v;
if(e[i].w<in[v]&&u!=v)
{
in[v]=e[i].w;
pre[v]=u;
}
}
in[root]=;
for(int i=;i<nv;i++)
if(in[i]==inf)
return ;
int cntnum=;
memset(vis,-,sizeof vis);
memset(Hash,-,sizeof Hash);
for(int i=;i<nv;i++)
{
ans+=in[i];
int v=i;
while(vis[v]!=i&&v!=root&Hash[v]==-)vis[v]=i,v=pre[v];
if(v!=root&&Hash[v]==-)
{
for(int u=pre[v];u!=v;u=pre[u])
Hash[u]=cntnum;
Hash[v]=cntnum++;
}
}
if(cntnum==)return ;
for(int i=;i<nv;i++)
if(Hash[i]==-)
Hash[i]=cntnum++;
for(int i=;i<ne;i++)
{
int v=e[i].v;
e[i].v=Hash[e[i].v];
e[i].u=Hash[e[i].u];
if(e[i].v!=e[i].u)e[i].w-=in[v];
}
nv=cntnum;
root=Hash[root];
}
return ;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int n,x,y,z;
while(cin>>n>>x>>y>>z){
if(n==&&x==&&y==&&z==)break;
for(int i=;i<=n;i++)cin>>p[i].x>>p[i].y>>p[i].z;
int cnt=;
for(int i=;i<=n;i++)
{
int k,s;
cin>>k;
while(k--){
cin>>s;
e[cnt].u=i;
e[cnt].v=s;
e[cnt].w=dis(i,s)*y;
if(p[s].z>p[i].z)e[cnt].w+=z;
cnt++;
}
}
for(int i=;i<=n;i++)
{
e[cnt].u=;
e[cnt].v=i;
e[cnt].w=x*p[i].z;
cnt++;
}
dirmst(,n+,cnt))
cout<<ans<<endl;
}
return ;
}
05-11 13:38