UESTC 1641 此情无计可消除，才下眉头，却上心头。 最小生成树、Kruskal

此情无计可消除，才下眉头，却上心头。 最小生成树、Kruskal

Source

2017 UESTC Training for Graph Theory

UESTC  1641 此情无计可消除，才下眉头，却上心头。

My Solution

题意：有一个长度为n的未知的01序列，询问区间[l,r](1<=l<=r<=n)的异或和代价为C[l][r]，
求通过询问得到该序列的最小代价.

最小生成树、Kruskal
建立n+1个虚拟点0到n，对于询问区间[l,r]，在l-1与r之间连边，边权为C[l][r]，
那么能得到该序列的极小询问集合会构成这n+1个点的一个生成树，代价为边权和。
证明(?)：
要得到n个位置的值，至少要询问n次
若询问集合构成的图存在回路
那么该回路对应的询问子集中任意一个询问的结果都可以由其它询问得到。
故询问集合构成的图有n条边且没有回路
也就是这n+1个点的一个生成树。
所以对这n+1个点跑一遍最小生成树即可。
时间复杂度：O(n^2)
空间复杂度：O(n^2)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e3 + 8;
const int MAXM = MAXN * MAXN;

struct edge{
    int u, v;
    LL w;
    edge(int u = 0, int v = 0, LL w = 0) : u(u), v(v), w(w) {}
}e[MAXM];
inline bool cmp(const edge &a, const edge &b){
    return a.w < b.w;
}

int fa[MAXN], _rank[MAXN];
inline void init(int n){
    for(int i = 0; i <= n; i++){
        fa[i] = i;
        _rank[i] = 0;
    }
}
inline int _find(int u){
    return fa[u] = fa[u] == u ? u : _find(fa[u]);
}
inline void _merge(int u, int v){
    int x = _find(u), y = _find(v);
    if(x == y) return;
    if(_rank[x] < _rank[y]){
        fa[x] = y;
    }
    else{
        fa[y] = x;
        if(_rank[x] == _rank[y]) _rank[x]++;
    }
}

inline LL kruskal(int n, int m){
    sort(e, e + m, cmp);
    int cnt = n, i;
    LL ans = 0;
    init(n);
    for(i = 0; i < m; i++){
        if(_find(e[i].u) != _find(e[i].v)){
            _merge(e[i].u, e[i].v);
            ans += e[i].w;
            cnt--;
            if(cnt == 1) break;
        }

    }
    return ans;
}
int main()
{
    #ifdef LOCAL
    freopen("h.txt", "r", stdin);
    //freopen("h.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    int n, m = 0, i, j;
    scanf("%d", &n);
    for(i = 1; i <= n; i++){
        for(j = i; j <= n; j++){
            e[m+j-i].u = i-1;
            e[m+j-i].v = j;
            scanf("%lld", &e[m+j-i].w);
        }
        m += n-i+1;
    }
    printf("%lldn", kruskal(n+1, m));



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx