HDU 4009 Transfer water 最小树形图

分析:建一个远点,往每个点连建井的价值(单向边),其它输水线按照题意建单向边

然后以源点为根的权值最小的有向树就是答案,套最小树形图模板

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
const int N=1e3+;
const int INF=0x7f7f7f7f;
struct Edge{
int u,v;
LL w;
}edge[N*N];
struct Node{
LL x,y,z;
}p[N];
LL in[N];
int id[N],vis[N],pre[N],n,m;
LL zhuliu(int rt,int n,int m){
int ret=;
while(){
for(int i=;i<=n;++i)in[i]=INF;
for(int i=;i<=m;++i){
if(edge[i].u!=edge[i].v&&edge[i].w<in[edge[i].v]){
pre[edge[i].v]=edge[i].u;
in[edge[i].v]=edge[i].w;
}
}
for(int i=;i<=n;++i)
if(i!=rt&&in[i]==INF)return -;
int cnt=;
memset(id,-,sizeof(id));
memset(vis,-,sizeof(vis));
in[rt]=;
for(int i=;i<=n;++i){
ret+=in[i];
int v=i;
while(vis[v]!=i&&id[v]==-&&v!=rt){
vis[v]=i;
v=pre[v];
}
if(v!=rt&&id[v]==-){
++cnt;
for(int u=pre[v];u!=v;u=pre[u])
id[u]=cnt;
id[v]=cnt;
}
}
if(cnt==)break;
for(int i=;i<=n;++i)
if(id[i]==-)id[i]=++cnt;
for(int i=;i<=m;++i){
int u=edge[i].u,v=edge[i].v;
edge[i].u=id[u];
edge[i].v=id[v];
if(id[u]!=id[v])edge[i].w-=in[v];
}
n=cnt;
rt=id[rt];
}
return ret;
}
LL dis(int i,int j){
return abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y)+abs(p[i].z-p[j].z);
}
int main()
{
LL X,Y,Z;
while(~scanf("%d%I64d%I64d%I64d",&n,&X,&Y,&Z)){
if(!n)break;
for(int i=;i<=n;++i)
scanf("%I64d%I64d%I64d",&p[i].x,&p[i].y,&p[i].z);
int cnt=;
for(int i=;i<=n;++i){
int k;
scanf("%d",&k);
for(int j=;j<=k;++j){
int u=i,v;
scanf("%d",&v);
if(u==v)continue;
++cnt;
edge[cnt].u=u,edge[cnt].v=v;
edge[cnt].w=dis(u,v)*Y;
if(p[u].z<p[v].z)edge[cnt].w+=Z;
}
}
for(int i=;i<=n;++i){
++cnt;
edge[cnt].u=n+;
edge[cnt].v=i;
edge[cnt].w=X*p[i].z;
}
LL ans=zhuliu(n+,n+,cnt);
printf("%I64d\n",ans);
}
return ;
}
上一篇:程序员应该是使用git


下一篇:angular 键盘事件绑定与过滤