[Kick Start] 2021 Round A (2)

对于度为 1 的点，说明该行/列，只有 1 个 -1，那么这个数据可以通过检验和还原，不需要任何的 cost ，我们在图中去掉所有这样的边，并且去掉之后，产生的新的度为 1 的点也需要同样的操作。

上述的性质表明，如果得到图是一颗树，那么所有的数据都能通过校验和还原。

比如下图的边 (row[1], col[2]) 和 (row[4], col[1]) 就是这样的边。

对于剩下的边所组成的图中，我们要去掉一些边，然后令整个图成为一棵树。显然，去除 (row[i], col[j]) 这条边时，需要耗费 B[i, j] 。

我们的目的是，去除权值最小的边，得到图的一棵树。换而言之，就是求出图的最大生成树 tree 。那么去除边所使用的权值就是 sum(graph) - sum(tree) .

代码实现

#include <iostream> #include <unordered_map> #include <vector> #include <queue> using namespace std; #define N 502 #define getrowid(r) (r) #define getcolid(c) (n + c) int nt; int A[N][N] = {{0}}, B[N][N] = {{0}}; int R[N] = {0}, C[N] = {0}; struct node_t { int x, y, cost; node_t(int xx, int yy, int cc) : x(xx), y(yy), cost(cc) {} bool operator<(const node_t &node) const { return cost < node.cost; } }; int find(vector<int> &root, int x) { return root[x] == -1 ? x : root[x] = find(root, root[x]); } uint64_t solve(int n) { unordered_map<int, unordered_map<int, int>> g; vector<int> degree(2 * n + 1, 0); int rid, cid; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (A[i][j] == -1) { rid = getrowid(i), cid = getcolid(j); g[rid][cid] = g[cid][rid] = B[i][j]; degree[rid]++, degree[cid]++; } } } // 去除度为 1 的点和这条边 for (int i = 1; i <= 2 * n; i++) { if (degree[i] == 1) { int vex = g[i].begin()->first; degree[i]--, degree[vex]--; g.erase(i); if (g.count(vex)) { g[vex].erase(i); if (g[vex].empty()) g.erase(vex); } } } // 使用 并查集 + Kruskal 求最大生成树 priority_queue<node_t> q; vector<int> root(2 * n + 1, -1); uint64_t sum = 0; for (auto &[x, m] : g) for (auto [y, c] : m) q.emplace(x, y, c), sum += c; // g 是邻接矩阵，里面有重复的边 sum /= 2; // cost 计算最大生成树 uint64_t cost = 0; while (!q.empty()) { auto [x, y, c] = q.top(); q.pop(); x = find(root, x), y = find(root, y); if (x != y) { root[y] = x; cost += c; } } return sum - cost; } int main() { cin >> nt; int n; for (int t = 1; t <= nt; t++) { cin >> n; uint64_t sum = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> A[i][j]; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> B[i][j]; for (int j = 1; j <= n; j++) cin >> R[j]; for (int j = 1; j <= n; j++) cin >> C[j]; printf("Case #%d: %llu\n", t, solve(n)); } }