题意
给出一张联通图,图上每个点有红蓝两色,给每一条边都赋一个权值,使得所有的红边构成一颗最小生成树,且权值是 \(1\) 到 \(m\) 的排列,求字典序最小的情况。
题解
对于一条蓝边,其权值一定小于除它以外全是红边的环上的所有红边的权值(有点绕),否则就构不成一颗生成树。
所以只需要按顺序枚举蓝边,然后按字典序染环上的红边,最后染这条蓝边即可。
namespace zqh {const int N = 500005;int n, m;vector<pair<int, int>> g[N];struct edge {int id, v;bool w;} e[N];int fa[N], dep[N], top[N], val[N], fid[N], k;void dfs(int id, int f, int dp) {fa[id] = f;dep[id] = dp;for (pii x : g[id]) {if (f == x.first) continue;fid[x.first] = x.second;dfs(x.first, id, dp + 1);}}void add(int id) {if (e[id].w) {if (!val[id]) {val[id] = ++k;
// cout << id << " t1o " << k << endl;}return;}int x = e[id].id, y = e[id].v, u = x, v = y;vector<int> tmp;while (top[u] != top[v]) {
// cout << u << " " << v << endl;
// cout << top[u] << " " << top[v] << endl;
// cout << fa[u] << " " << fa[v] << endl;if (dep[top[u]] > dep[top[v]]) {if (!val[fid[top[u]]]) tmp.push_back(fid[top[u]]);u = fa[top[u]];} else {if (!val[fid[top[v]]]) tmp.push_back(fid[top[v]]);v = fa[top[v]];}}sort(tmp.begin(), tmp.end());for (int x : tmp) {val[x] = ++k;
// cout << x << " t2o " << k << endl;}val[id] = ++k;
// cout << id << " t3o " << k << endl;int p = u, q = v;u = x, v = y;while (top[u] != top[v]) {if (dep[top[u]] > dep[top[v]]) {int tmp2 = u;u = fa[top[u]];top[tmp2] = top[p];} else {int tmp2 = v;v = fa[top[v]];top[tmp2] = top[q];}}}void init() {cin >> n >> m;for (int i = 1; i <= m; i++) {int id, v;bool w;cin >> id >> v >> w;e[i] = {id, v, w};if (!w) continue;g[id].push_back({v, i});g[v].push_back({id, i});}dfs(e[1].id, 0, 1);}void solve() {for (int i = 1; i <= n; i++) {top[i] = i;}for (int i = 1; i <= m; i++) {add(i);}for (int i = 1; i <= m; i++) {cout << val[i] << " ";}}void main() {init();solve();}
}