模拟赛|【模拟赛】【最小生成树】2021.8.10.B 模拟赛|最小生成树|最小生成树

【模拟赛|【模拟赛】【最小生成树】2021.8.10.B】
目录

题目描述
代码

题目描述最小生成树模板
即使不只派出一个通讯员，也可以全部点连向0号点处理
代码

#include #include #include #include #define ll long long using namespace std; struct wh_ { ll w, h, k; }wh[1000250]; ll t, n, k, tot, l, sum; ll Fa[2005]; void hw(ll x, ll y, ll z) { wh[++t] = (wh_) { x, y, z}; }bool nm(wh_ i, wh_ j) { return i.k < j.k; }ll find(ll k) { if(k != Fa[k])return Fa[k] = find(Fa[k]); else return k; }ll read() { ll x = 0, r = 1; char c = getchar(); while(c < '0' || c > '9'){ if(c == '-')r = -1; c = getchar(); } while('0' <= c && c <= '9')x = x * 10 + c - 48, c = getchar(); return x * r; }int main() { n = read(); for(ll i = 1; i <= n; ++i) for(ll j = 1; j <= n; ++j) {k = read(); if(i > j)hw(i, j, k); } for(ll i = 1; i <= n; ++i) {k = read(); hw(0, i, k), Fa[i] = i; } tot = 0, l = 0; sort(wh + 1, wh + t + 1, nm); while(tot < n && ++l) {ll x = wh[l].w, y = wh[l].h; ll xx = find(x); ll yy = find(y); if(xx == yy)continue; Fa[max(xx, yy)] = min(xx, yy); tot++, sum += wh[l].k; } printf("%lld", sum); return 0; }