hdoj 4009 Transfer water 【无源点最小树形图】【好题】

冷不防 2022-08-13 14:42 41阅读 0赞

题目：[hdoj 4009 Transfer water][]

题意：题目有点长，说是有个村子，有 n 户人家要用水，他们加的位置用三维坐标来表示（x，y，z），他们有两种选择：

1：自己挖一口井，花费为 z \* cost\_x

2：从别人家接个水管引过来，化为为距离 \* cost\_y，如果要引的地方比当前地方低的话，还要买一个水泵，花费cost\_z。

距离算法**|x2‐x1|+|y2‐y1|+|z2‐z1|.**

**然后求让所有的人都有用的水的最小花费、**

**分析：发现它是一个求最小生成树的题目，但是关键点有二**

**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\n",e[i].from,e[i].to,e[i].dis);
    //        }
            int ans = zhuliu(n-1);
            printf("%d\n",ans);
            e.clear();
        }
        return 0;
    }

[hdoj 4009 Transfer water]: http://acm.hdu.edu.cn/showproblem.php?pid=4009