「Usaco2008 Oct」灌水 - 最小生成树

氵一篇 Blog

Shq 只会刷水题了 /kel

题目链接

1601. [Usaco2008 Oct]灌水

Description

Farmer John 已经决定把水灌到他的 $n(1\le n\le 300)$ 块农田，农田被数字 $1$ 到 $n$ 标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库

建造一个水库需要花费 $w_i(1\le w_i\le10^5)$ , 连接两块土地需要花费$P_{ij}(1\le p_{ij}\le10^5,p_{ij}=p_{ji},p_{ii}=0)$. 计算 Farmer John 所需的最少代价。

Input

*第一行：一个数 $n$

*第二行到第 $n+1$ 行：第 $i+1$ 行含有一个数 $w_i$

*第 $n+2$ 行到第 $2n+1$ 行：第 $n+1+i$ 行有 $n$ 个被空格分开的数，第 $j$ 个数代表 $p_{ij}$

Output

*第一行：一个单独的数代表最小代价.

Sample Input

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

Sample Output

9

输出详解：

Farmer John在第四块土地上建立水库，然后把其他的都连向那一个，这样就要花费 $3+2+2+2=9$

---

题解

sb 最小生成树题

建一个点向所有点连一条权值为 $w_i$ 的边

剩下的按照题目来就好了（

Code

struct Edge {
    int to, dist;
    int from;

    Edge () {}
    Edge (int _from, int _to, int _dist) : from(_from) , to(_to) , dist(_dist) {}

    ~Edge () {}

    bool operator < (const Edge &other)const {
        return dist < other.dist;
    }
};

const int MAXN = 100010;

int tot;
Edge edges[MAXN];

inline void addEdge (int u, int v, int w) {
    edges[tot++] = Edge(u, v, w);
}

ll n;
ll data[MAXN];

int fa[MAXN];

inline void init () {
    up (i, 1, n) fa[i] = i;
}

inline int find (int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

inline void merge (int x, int y) {
    fa[x] = y;
}

int main(int argc, char const *argv[]) {
    srand(time(NULL) + rand()); srand(time(NULL) + rand() + rand() * rand()); srand(time(NULL) + rand() + rand() ^ rand() * rand());
    while (rand() & 1) n = rand() * rand();
    n = SlowRead();

    ll tmp = n + 1;

    up (i, 1, n) data[i] = SlowRead();

    int w;
    up (u, 1, n)
        up (v, 1, n) {
            w = SlowRead();
            addEdge (u, v, w);
        }
    
    up (i, 1, n) addEdge (i, tmp, data[i]);

    std::sort (edges, edges + tot);

    init();

    int ans = 0;
    up (i, 0, tot - 1) {
        //printf("%d->%d is %d\n", edges[i].from, edges[i].to, edges[i].dist);
        int fx = find(edges[i].from);
        int fy = find(edges[i].to);
        if (fx != fy) {
            merge (fx, fy);
            ans += edges[i].dist;
        }
    }

    Print(ans);
    return 0;
}

谜之音：那么氵的题目还氵 Blog（

本文是 2019/1/9 20:58 写完的，不知道啥时候能发出去（