跳转至

2022-0504-MST

USACO 2015 Feb S. Superbull 提高 https://www.luogu.com.cn/problem/P4826
Slim Span, ACM/ICPC Japan 2007 提高+ https://www.luogu.com.cn/problem/UVA1395
POJ2349 Arctic Network 提高 http://bailian.openjudge.cn/practice/2349/
[JSOI2010]部落划分 提高 https://www.luogu.com.cn/problem/P4047
USACO 2016 Feb G. Fenced In 提高 https://www.luogu.com.cn/problem/P6171
USACO 2019 Open G. I Would Walk 500 Miles 提高 https://www.luogu.com.cn/problem/P5425
Buy or Build, SWERC 2005, UVa1151 提高+ https://www.luogu.com.cn/problem/UVA1151

Superbull

/**
 * @file luogu/4826/main.cpp
 * @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
 * @brief 一共有 n 头牛参加淘汰赛,每次比赛的分数为两头牛 id 的按位异或,
 * 每次比赛后淘汰一头牛,问最大的分数总和
 *
 * 1. 有 n 头牛
 * 2. 有 n-1 场比赛
 * 3. 对每一头牛,除了最后的赢家,有且仅有一头战胜自己的牛
 * 4. 最后的赢家没有战胜它的牛
 *
 * 很显然是树的性质,计算每两头牛之间比赛的分数,求最大生成树。
 *
 * @version 0.1
 * @date 2022-05-01
 *
 * @copyright Copyright (c) 2022
 *
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2010;
ll id[N];
int par[N * N];
struct edge {
  int u, v;
  ll cost;
  bool operator<(const edge &b) const { return cost > b.cost; } // 反向排序
};
vector<edge> match;
int n;
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> id[i];
  // 枚举,让牛两两比赛
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      match.push_back({i, j, id[i] ^ id[j]});
    }
  }
  // Kruskal 最小生成树
  ll ans = 0;
  int cnt = 0;
  for (int i = 0; i < n * n; ++i) par[i] = i;
  sort(match.begin(), match.end());
  for (int i = 0; i < match.size(); ++i) {
    auto [u, v, cost] = match[i];
    u = find(u), v = find(v);
    if (u == v) continue;
    par[u] = v;
    ans += cost;
    cnt++;
    if (cnt == n - 1) break;
  }
  cout << ans << endl;
}

Slim Span

/**
 * @file uva/1395/main.cpp
 * @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
 * @brief
 * 给定一张图,求一棵生成树,使其最大边权与最小边权差最小,输出它们的差值
 * 如果图存在生成树,输出生成树的差值最小的;否则,输出-1。
 *
 * 对于每一个边都从它开始Kruskal一遍并更新答案
 * @version 0.1
 * @date 2022-05-01
 *
 * @copyright Copyright (c) 2022
 *
 */
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct edge {
  int u, v, w;
  bool operator<(const edge &b) const { return w < b.w; }
} e[N];
typedef long long ll;
int n, m;
int par[N];

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

int maxedge;
bool kruskal(int start_from) {
  for (int i = 1; i <= n; ++i) par[i] = i;
  int cnt = 0;
  maxedge = -1;
  for (int i = start_from; i <= m; ++i) {
    auto [u, v, w] = e[i];
    u = find(u), v = find(v);
    if (u == v) continue;
    par[u] = v;
    if (++cnt == n - 1) {
      // 保存最大边权
      maxedge = w;
      return true;
    }
  }
  return false;
}

int main() {
  while (scanf("%d%d", &n, &m) != EOF && n) {
    for (int i = 1; i <= m; ++i) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    int ans = 0x3f3f3f3f;
    sort(e + 1, e + m + 1);
    for (int i = 1; i <= m; ++i) {
      // 从第 i 条边开始计算生成树
      if (kruskal(i)) {
        ans = min(ans, maxedge - e[i].w);
      }
    }
    cout << (ans == 0x3f3f3f3f ? -1 : ans) << endl;
  }
}

Arctic Network

/**
 * @file poj/2349/main.cpp
 * @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
 * @brief 每一个outpost都会配有电波接收器,一些outpost会配有卫星接收器
 * 电波接收器有一定工作范围,都为D;卫星的工作范围是无限。
 * 求最小的D使得任意两点可以直接或间接通信。
 *
 * 通过连接 n - s 条边使得图有 s 个连通分量
 * 输出MST第 n - s 条边的权重即可
 *
 * @see <http://bailian.openjudge.cn/practice/2349/>
 * @see <http://bailian.openjudge.cn/practice/solution/34259329/>
 * @version 1.0
 * @date 2022-05-02
 *
 * @copyright Copyright (c) 2022
 *
 **/

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int x[N], y[N];
int s, n;
struct edge {
  int u, v;
  double d;
  bool operator<(const edge &b) const { return d < b.d; }
};
vector<edge> E;
inline double dist(int u, int v) {
  double dx = x[u] - x[v], dy = y[u] - y[v];
  return sqrt(dx * dx + dy * dy);
}
int par[N];
inline int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }

int main() {
  int tc;
  cin >> tc;
  while (tc--) {
    cin >> s >> n;
    for (int i = 0; i <= n; ++i) par[i] = i;
    E.clear();  // 记得清全局变量

    for (int i = 0; i < n; ++i) {
      cin >> x[i] >> y[i];
    }
    // 计算点对距离并排序
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j) E.push_back({i, j, dist(i, j)});
    sort(E.begin(), E.end());

    int cnt = 0;
    for (auto [u, v, cost] : E) {
      u = find(u), v = find(v);
      if (u == v) continue;
      par[u] = v;
      if (++cnt == n - s) {
        printf("%.2lf\n", cost);
        break;
      }
    }
  }
}

部落划分

并查集,不断合并最近的,直到剩\(k\)个集合。

/**
 * P4047 [JSOI2010]部落划分
**/

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+8;

int n, k;
int x[maxn], y[maxn];
struct p {
  int u, v, dist;
  p() = default;
  p(int a, int b):u(a), v(b){
    int dx = abs(x[a]-x[b]), dy=abs(y[a]-y[b]);
    dist = dx*dx+dy*dy;
  }
  bool operator < (const p &b) const {return dist<b.dist;}
}dist[maxn*maxn];
int tot, merged;
int par[maxn];
void init() {for(int i=1; i<n; ++i) par[i]=i;}
int find(int x) {return x==par[x]?x:par[x]=find(par[x]);};
void unite(int u, int v) {par[find(u)]=find(v);}
bool same(int u, int v) {return find(u)==find(v);}

int main() {
  scanf("%d%d\n", &n, &k);
  for(int i=0; i<n; ++i) {
    scanf("%d%d", x+i, y+i);
  }
  init();
  for(int i=0; i<n; ++i) {
    for(int j=i+1; j<n; ++j) {
      dist[tot++] = p(i, j);
    }
  }
  sort(dist, dist+tot);
  int nclans = n;
  int cnt;
  for(cnt=0; cnt<tot; ++cnt) {
    // Make it C++11 Compatible
    // auto [u, v, d] = dist[cnt];
    auto u = dist[cnt].u;
    auto v = dist[cnt].v;
    auto d = dist[cnt].dist;
    if(!same(u, v)) {
      unite(u, v);
      nclans--;
      if(nclans==k) break;
    }
  }
  for(;cnt<tot; ++cnt) {
    // auto [u, v, d] = dist[cnt];
    auto u = dist[cnt].u;
    auto v = dist[cnt].v;
    auto d = dist[cnt].dist;
    if(same(u, v)) continue;
    else {
      printf("%.2f\n", sqrt(d));
      break;
    }
  }
}

Fenced In

/**
 * @file luogu/6171/main.cpp
 * @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
 * @brief
 * @version 0.1
 * @date 2022-05-01
 * @url https://www.luogu.com.cn/record/74966952
 *
 * @copyright Copyright (c) 2022
 *
 */

#include <bits/stdc++.h>
using namespace std;
const int N = 2004;
int pa[N * N];
int find(int x) { return x == pa[x] ? x : pa[x] = find(pa[x]); }
bool merge(int x, int y) {
  x = find(x), y = find(y), pa[x] = y;
  return x != y;
}
int a, b, m, n;
int enc(int r, int c) { return r * m + c; }
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> a >> b >> n >> m;
  vector<int> w(n + 1), h(m + 1);
  for (int i = 0; i < n; ++i) cin >> w[i];
  sort(w.begin(), w.end());
  for (int i = 0; i < n; ++i) w[i] = w[i + 1] - w[i];
  w[n] = b - w[n];

  for (int i = 0; i < m; ++i) cin >> h[i];
  sort(h.begin(), h.end());
  for (int i = 0; i < m; ++i) h[i] = h[i + 1] - h[i];
  h[m] = a - h[m];

  sort(w.begin(), w.end()), sort(h.begin(), h.end()), n++, m++;
  for (int i = 0; i < n * m; ++i) pa[i] = i;
  long long ans = 0;
  for (int vi = 0, hi = 0; vi < n || hi < m;) {
    if (hi == m || vi < n && w[vi] < h[hi]) {
      for (int i = 0; i < m - 1; ++i) {
        if (merge(enc(vi, i), enc(vi, i + 1))) ans += w[vi];
      }
      vi++;
    } else {
      for (int i = 0; i < n - 1; ++i) {
        if (merge(enc(i, hi), enc(i + 1, hi))) ans += h[hi];
      }
      hi++;
    }
  }
  cout << ans << endl;
}

Would Walk 500 Miles

玄学:开-O2会错

#include <bits/stdc++.h>
using namespace std;
const int NN = 7500;
int N, K, Vis[NN];
#define _all(i, a, b) for (int i = (a); i <= (int)(b); ++i)
using LL = long long;
const LL MOD = 2019201997, A = 2019201913LL, B = 2019201949LL;
LL D[NN];
LL prim() {  // Prim/Jarnik MST algorithm
  _all(i, 1, N) D[i] = MOD;
  _all(iter, 1, N) {
    int mi = 0;
    _all(i, 1, N) if (!Vis[i] && (mi == 0 || D[i] < D[mi])) mi = i;
    Vis[mi] = 1;
    _all(i, 1, N) if (!Vis[i]) D[i] =
        min(D[i], (A * min(mi, i) % MOD + B * max(mi, i)) % MOD) % MOD;
  }
  sort(D + 1, D + N + 1);
  return D[N + 1 - K];
}
int main(void) {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> N >> K;
  cout << prim() << "\n";
  return 0;
}

Buy or Build

#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 10, Q = 8;
int n, x[N], y[N], cost[N];
vector<int> subn[Q];
int pa[N];
int findset(int x) { return pa[x] != x ? pa[x] = findset(pa[x]) : x; }

struct Edge {
  int u, v, d;
  Edge(int u, int v, int d) : u(u), v(v), d(d) {}
  bool operator<(const Edge& rhs) const { return d < rhs.d; }
};

/**
 * @brief 求MST
 *
 * initialize `pa` and sort `e` before calling this method.
 * `cnt` is the current number of components
 *
 * @param cnt 当前连通分量的个数
 * @param e 可用的边集
 * @param used 返回已使用的边集
 * @return 新加入MST的边的权重之和
 */
int MST(int cnt, const vector<Edge>& e, vector<Edge>& used) {
  if (cnt == 1) return 0;
  int m = e.size();
  int ans = 0;
  used.clear();
  for (int i = 0; i < m; ++i) {
    int u = findset(e[i].u), v = findset(e[i].v);
    int d = e[i].d;
    if (u != v) {
      pa[u] = v;
      ans += d;
      used.push_back(e[i]);
      if (--cnt == 1) break;
    }
  }
  return ans;
}

int main() {
  int T, q;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &q);
    for (int i = 0; i < q; ++i) {
      int cnt;
      scanf("%d%d", &cnt, &cost[i]);
      subn[i].clear();  // 清掉上一次的,别忘了
      while (cnt--) {
        int u;
        scanf("%d", &u);
        subn[i].push_back(u - 1);
      }
    }
    for (int i = 0; i < n; ++i) scanf("%d%d", &x[i], &y[i]);

    vector<Edge> e,  // 边集
        need;  // 如果某条边不在MST中,这条边也不会出现在买了子网后的生成树中。
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j) {
        int c = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
        e.push_back(Edge(i, j, c));
      }

    for (int i = 0; i < n; ++i) pa[i] = i;
    sort(e.begin(), e.end());

    int ans = MST(n, e, need);  // 1. 一个都不买
    // 2. 至少买一个
    for (int mask = 1; mask < (1 << q); ++mask) {
      // 买下子网,将子网内部连到一起
      for (int i = 0; i < n; ++i) pa[i] = i;
      int cnt = n,  // 最开始,有n个连通分量
          c = 0;    // 本次花费
      for (int i = 0; i < q; ++i)
        if (mask & (1 << i)) {
          c += cost[i];  // 买子网,加到同一个连通分量中
          for (int j = 1; j < subn[i].size(); ++j) {
            int u = findset(subn[i][j]), v = findset(subn[i][0]);
            if (u != v) {
              pa[u] = v;
              cnt--;
            }
          }
        }
      vector<Edge> dummy;

      // 子网消耗 + 继续连通
      ans = min(ans, c + MST(cnt, need, dummy));
    }
    printf("%d\n", ans);
    if (T) printf("\n");
  }
  return 0;
}