BZOJ3714《Kuglarz》

八月 15, 2019 3236

这是最小生成树？

Description

魔术师的桌子上有n个杯子排成一行，编号为1,2,…,n，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。花费c_ij元，魔术师就会告诉你杯子i,i+1,…,j底下藏有球的总数的奇偶性。
采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？

Input

第一行一个整数n(1<=n<=2000)。
第i+1行(1<=i<=n)有n+1-i个整数，表示每一种询问所需的花费。其中c_ij（对区间[i,j]进行询问的费用，1<=i<=j<=n,1<=c_ij<=10^9）为第i+1行第j+1-i个数。

Output

输出一个整数，表示最少花费。

Sample Input

1
2
3
4
5
6
5  
1 2 3 4 5  
4 3 2 1  
3 4 5  
2 1  
5

Sample Output

1
7

解析

从代码里复制过来的

知道两段杯子的奇偶性，相当于知道左边杯子左边的缝到右边杯子右边的缝到奇偶性

然后显然这个东西具有传递性，即知道缝a到缝b、缝b到缝c的奇偶性 \Leftrightarrow 缝a到缝c的奇偶性

知道所有数列要保证缝两两之间的奇偶性都要知道

那么就可以把缝抽象成点，缝两两之间的奇偶性信息抽象成边，边权为询问的代价

一遍最小生成树完事

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//
//  BZOJ3714.cpp
//  Debugging
//
//  Created by HandwerSTD on 2019/8/15.
//  Copyright © 2019 HandwerSTD. All rights reserved.
//

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rap(a,s,t,i) for (int a = s; a <= t; a += i)
#define basketball(a,t,s,i) for (int a = t; a > s; a -= i)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

typedef long long int lli;

int getint() { int x; scanf("%d", &x); return x; }
lli getll() { long long int x; scanf("%lld", &x); return x; }

/**
 * 知道两段杯子的奇偶性，相当于知道左边杯子左边的缝到右边杯子右边的缝到奇偶性
 * 然后显然这个东西具有传递性，即知道缝a到缝b、缝b到缝c的奇偶性 <=> 缝a到缝c的奇偶性
 * 知道所有数列要保证缝两两之间的奇偶性都要知道
 * 那么就可以把缝抽象成点，缝两两之间的奇偶性信息抽象成边，边权为询问的代价
 * 一遍最小生成树完事
 */

const int MAXN = 2000 + 10;

struct UnionFind {
    int u[MAXN];
    
    UnionFind() { memset(u, 0, sizeof u); }
    void Init(int x) {
        for (int i = 1; i <= x; ++i) u[i] = i;
    }
    int Find(int x) { return u[x] == x ? x : (u[x] = Find(u[x])); }
    bool Union(int x, int y) {
        x = Find(x); y = Find(y);
        if (x == y) return false;
        u[x] = y;
        return true;
    }
} U;

struct Edge {
    int u, v, w;
    
    Edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
    bool operator < (const Edge &that) const {
        return w < that.w;
    }
};

int n, cnt;
lli ans;
std::vector<Edge> edge;

void Kruskal() {
    int tot = 0;
    // std::sort(edge + 1, edge + 1 + cnt);
    std::sort(edge.begin(), edge.end());
    for (int i = 0; i < cnt; ++i) {
        if (U.Union(edge[i].u, edge[i].v)) {
        // printf("choosed edge[%d] = { %d %d %d }\n", i, edge[i].u, edge[i].v, edge[i].w);
            ++tot; ans += 1ll * edge[i].w;
        }
    }
}

int main() {
    n = getint();
    U.Init(n + 1);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            int x = getint();
            edge.push_back(Edge(i, j, x));
            
        }
    }
    cnt = (int) edge.size();
    Kruskal();
    printf("%lld\n", ans);
    return 0;
}