[题解 hduoj-7522] 2024HDU 暑假多校7 - cats 的最小生成树

原题链接

题意

有一个有重边的无向图, 每次找到它的最小生成树, 并删除生成树的边, 直到不存在最小生成树, 问被每条边在第几次被删除.

思路

考虑用类似 Kruskal 算法, 但是是遍历一遍所有边, 同时处理出来所有的生成树.

具体这样做:

1. 如 Kruskal 一样, 把所有边按边权排序, 依次遍历
2. 当遍历到 u, v 两个节点之间的边时, 二分查找他们在第几个生成树中不连通 ( 这里要开许多并查集数组), 加入他们找第 x 个生成树中不连通, 那他们在 x 之后的生成树中一定不连通.
3. 找到后, 就把这条边加入这个生成树中, 给这条边打上标记.
4. 最后统计每个生成树有多少条边, 有 n-1 条时, 这个生成树就是合法的. 输出生成树的所有边.

代码:

#define int long longstruct node {int u, v, w, id, vis;bool operator<(node x)const {return w > x.w;}
};
void solve(int _) {int n, m, v, u;cin >> n >> m;vector<node>eg(m + 1);priority_queue<node>q;vector<vector<int>>fa;fa.emplace_back(vector<int>(n + 1, 0));auto find = [&](auto self, int mid, int x) {if (fa[mid][x] == x)return x;return fa[mid][x] = self(self, mid, fa[mid][x]);};for (int i = 1; i <= m; ++i) {cin >> v >> u;eg[i] = {v, u, i, i, 0};q.emplace(eg[i]);}vector<int>vis(n + 1, 0);int Max = 0;while (!q.empty()) {auto [u, v, w, id, viss] = q.top();q.pop();if (vis[v] > vis[u])swap(v, u);int l = 0, r = vis[v];while (l < r) {int mid = (r + l + 1) / 2;if (find(find, mid, v) == find(find, mid, u)) l = mid;else r = mid - 1;}r++;vis[v] = max(vis[v], r);vis[u] = max(vis[u], r);if (r + 1 > fa.size()) {fa.emplace_back(vector<int>(n + 1));iota(fa[r].begin(), fa[r].end(), 0);}fa[r][find(find, r, v)] = find(find, r, u);eg[id].vis = r;Max = max({Max, vis[v], vis[u]});}vector<int>cnt(Max + 1, 0);for (int i = 1; i <= m; ++i) {cnt[eg[i].vis]++;debug(eg[i].vis)}for (int i = 1; i <= m; ++i) {if (cnt[eg[i].vis] >= n - 1)cout << eg[i].vis << " \n"[i == m];else cout << -1 <<  " \n"[i == m];}
}
signed main()
{ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);int _ = 1;cin >> _;while (_--) {solve(_);}
}