题目传送门:K-Link-Cut Tree_第46屆ICPC 東亞洲區域賽(澳門)(正式賽) (nowcoder.com)
题目大意
有T个测试样例。
给定n个点,m条边,第i条边的权值为2的i次方,求图中权值之和最小的环的边的编号(从小到大)。
思路
看到2的i次方,不难想到用贪心,从小到大(也就是按照输入顺序)遍历所有边,一旦出现环,就直接输出这个环的边的编号就行了,一定是权值和最小的。
这里可以用并查集判断是否有环,方法是如果新的边{x, y}已经相连那么连接之后就会形成第一个环,然后忽略后面的输入,再用dfs配合栈来将环输出。
注意:这题十分毒瘤,我的root函数用while循环来写就TLE了(进行了路径压缩),但是用递归方式写就不会T,真的无语了。

代码
#include <bits/stdc++.h> #define pb push_back #define int long long #define fi first #define se second using namespace std; inline int readInt() { int s = 0,w = 1;char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();} while('0' <= ch && ch <= '9')s = s * 10 + ch - '0',ch = getchar(); return s * w; } typedef pair<int, int> PII; const int maxn = 1e5 + 10; int pre[maxn]; vector<pair<int, int> > g[maxn]; int root(int x) { if(pre[x] == x)return x; return pre[x] = root(pre[x]); } int stk[maxn], top = 0; bitset<maxn> vis; void dfs(int ed, int x, int fa) { vis[x] = true; if(ed == x) { sort(stk + 1, stk + top + 1); for (int i = 1; i <= top; ++i) printf("%d%c", stk[i], i == top ? '\n' : ' '); } for(auto i : g[x]) { int y = i.fi, id = i.se; if (y == fa || vis[y])continue; stk[++top] = id; dfs(ed, y, x); --top; } } void solve() { int n = readInt(), m = readInt(); for(int i = 1;i <= n; ++ i) { pre[i] = i; g[i].clear(); vis[i] = 0; } int st = 0;//起始点 bool tag = 0;//已经有环 for(int i = 1;i <= m; ++ i) { int x = readInt(), y = readInt(); if(tag)continue; g[x].pb({y, i}); g[y].pb({x, i}); if(root(x) == root(y)) { st = x; tag = 1; } pre[root(x)] = root(y); } if(tag) { top = 0; for(auto i : g[st]) { stk[++ top] = i.se; dfs(st, i.fi, st); -- top; } } else printf("-1\n"); } signed main() { int T = readInt(); while(T --)solve(); return 0; }
Comments NOTHING