A simple Blog for wyx I've been down the bottle hoping.
3714: [PA2014]Kuglarz 最小生成树
发表于: | 分类: Oi | 评论:0 | 阅读:186

首先这个东西只知道奇数还是偶数,显然我们最后只有确定到长度为一的区间才算是确定了所有需要确定的东西

那么这个问题就变得水了很多,因为我们只需要从低到高贪心选出你想选的区间即可

如果化成图论模型的话就是最小生成树

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2000+5;
const int M = N * N / 2;
typedef long long LL;
int n;

struct data{
    int from,to,val;
    bool operator < (const data &z)const{
        return val < z.val;
    }
}edge[M];

int fa[N];

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

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9') {x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main() {
    int n = read(), tot = 0;
    register int i,j;
    for(i=1;i<=n;++i)
        for(j=i;j<=n;++j) 
            edge[++tot].from = i, edge[tot].to = j+1, edge[tot].val = read();
    sort(edge+1,edge+tot+1);
    LL ans = 0;
    for(int i=1;i<=n+1;++i) fa[i] = i;
    for(int i=1;i<=tot;++i) {
        if(find(edge[i].from) != find(edge[i].to)) {
            fa[find(edge[i].to)] = find(edge[i].from);
            ans += edge[i].val;
        }
    }
    cout << ans << endl;        
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP