HDU 4009 Transfer water(Minimun tree-shape graph)

Description

N个房子搬到山上，要解决供水问题有两种方案：

①自己打井，耗钱 (X * 房子高度)

②从别家引水，耗钱 (Y * 两房子的曼哈顿距离)，如果源较低，再加一个水泵钱Z

求解决所有房子供水问题的最小花费

Analyze

不难发现是一个不定根的题目 -> 增加一个伪根。

但是在建图时，“饮水”的边正常建立，“打井”如何处理？看似“自给自足”让人想到自环，可两者没什么关系，添自环不解决问题。

而且对于独立点，即使不能生成最小树形图，也可以”打井”完成任务，这种情况如何求最小花费？

Solution

将伪根连向各点的边的权值设为该点打井花费！

实现了“打井”与“引水”一视同仁，可计算最小花费。

什么完美的建模思想！

这跟之前做过的一道最短路相似，那题是“昂贵的聘礼”，给定了终点，也是不定根(起点任选)，求最短路。但是不仅边有权值，每个点也有权值，意味着从每个点出发的花费不同，这时建立超级源点连向各点的边的权值就应该设为各点权值！

这是一类“不定根 && 点有权值”的图论题目

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
const int INF = 0x3f3f3f3f;

int n, m, X, Y, Z, id[N], pre[N], vis[N], in[N], x[N], y[N], z[N];

struct edge
{
    int u, v, w;
}e[N * N];///Pay attention to the number of edges!

int getDis(int a, int b)
{
    return Y * (abs(x[a] - x[b]) + abs(y[a] - y[b]) + abs(z[a] - z[b])) + (z[b] > z[a] ? Z :0);
}

int zhuliu(int root)
{
    int u, v, res = 0;
    while(true)
    {
        ///1.Set of in
        for(int i = 1; i <= n; ++i)
            in[i] = -1;
        for(int i = 1; i <= m; ++i)
            if(e[i].u != e[i].v && (e[i].w < in[ e[i].v ] || in[ e[i].v ] < 0))
                in[ e[i].v ] = e[i].w, pre[ e[i].v ] = e[i].u;
        for(int i = 1; i <= n; ++i)
            if(i != root && in[i] < 0)
                return -1;

        ///2.Directed circle
        int cnt = 1;
        memset(id, -1, sizeof(id));
        memset(vis,-1, sizeof(vis));
        in[root] = 0;
        for(int i = 1; i <= n; ++i)
        {
            res += in[i];
            v = i;
            while(id[v] == -1 && v != root && vis[v] != i)
                vis[v] = i, v = pre[v];
            if(id[v] == -1 && v != root)///   vis[v] == i
            {
                for(u = pre[v]; u != v; u = pre[u])
                    id[u] = cnt;
                id[v] = cnt++;
            }
        }

        ///3.No circle -> Over
        if(cnt == 1)
            break;

        ///4.Process other nodes ,and then "shrink".
        for(int i = 1; i <= n; ++i)
            if(id[i] == -1)
                id[i] = cnt++;
        for(int i = 1; i <= m; ++i)
        {
            v = e[i].v;
            e[i].u = id[ e[i].u ];
            e[i].v = id[ e[i].v ];
            if(e[i].u != e[i].v)
                e[i].w -= in[v];///This v is the original v!
        }
        n = cnt - 1;
        root = id[root];
    }
    return res;
}

int main()
{
    while(~scanf("%d %d %d %d", &n, &X, &Y, &Z) && !(n + X + Y + Z == 0))
    {
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d %d %d", &x[i], &y[i], &z[i]);
            e[i].u = n + 1, e[i].v = i, e[i].w = z[i] * X;
        }

        m = n;
        int tem, num;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &num);
            while(num--)
            {
                scanf("%d", &tem);
                e[++m].u = i, e[m].v = tem, e[m].w = getDis(i, tem);
            }
        }

        int ans = zhuliu(++n);
        printf("%d\n", ans);
    }
    return 0;
}