abc065d <贪心+最小生成树> [lambda表达式]

D - Built?

// https://atcoder.jp/contests/abc065/tasks/arc076_b
// 贪心+最小生成树
// 关键在于意识到, 连接x或y相邻的边代价最小, 因而无需考虑全部的边, 仅需考虑这些相邻边即可(贪心)
// 学习:
//  1. lambda写法  https://www.cnblogs.com/yaya12138/p/11815475.html
//  2. unit() 的代码风格 
//  3. x[], y[] 代码风格 
//  4. 对索引pt[]sort的代码风格
//  5. 要习惯定义结构体, 这样更方便
// 参考 https://www.bilibili.com/read/cv24439598
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;

struct Edge
{
    int u, v, w;
};

int x[N], y[N];  // 第i个输入的x和y
int pt[N];  // 索引
int fa[N];  // 并查集

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

void solv()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> x[i] >> y[i];
        fa[i] = pt[i] = i;
    }

    vector<Edge> edge;
    // 按x排序, 达到x方向的相邻边, 计算权重, 记录
    sort(pt+1, pt+1+n, [&](int &a, int &b) {return x[a] < x[b]; });
    for (int i = 1; i < n; i ++) edge.push_back({pt[i], pt[i+1], abs(x[pt[i]] - x[pt[i+1]])});
    // y
    sort(pt+1, pt+1+n, [&](int &a, int &b) {return y[a] < y[b]; });
    for (int i = 1; i < n; i ++) edge.push_back({pt[i], pt[i+1], abs(y[pt[i]] - y[pt[i+1]])});
    
    // Kruskal
    sort(edge.begin(), edge.end(), [&] (Edge &a, Edge &b) {return a.w < b.w; });
    LL ans = 0;
    for (auto &e: edge)
    {
        int a = find(e.u), b = find(e.v);
        if (a != b)
        {
            fa[a] = b;
            ans += e.w;
        }
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}