Codeforces Round 923 (Div. 3)

F：给定一张一般图，不保证连通，定义一个简单环的权值是环中最小边的权值，求图中最小环的权值和具体由哪些点组成。

Sol：首先需要思考的是怎么求出最大权值？我们考虑用克鲁斯卡尔算法的思想对边权排序，考虑逐步加入图中，一旦合并失败就说明当前边构成了这个环的最小边，我们维护答案，同时记录左右端点。

第二阶段我们需要利用最小边的两个点把目标环的所有点找出来。我们用标记数组保证点不走回头路，用flag保证函数递归栈退出，不再执行循环。从L开始dfs，遇到R的时候就统计答案。

  • 实现的地方还有一个困难就是对于不在环上的点可能需要加入再删除，这样比较啰嗦，提供一种jly用bool返回值的写法。当更深的递归函数返回结果时，当前的点才加入path中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//为了给小的边机会，我们当然应该将边权从大到小加进图中
struct edge{int u,v,w;};
bool cmp(edge c,edge d){return c.w>d.w;}
vector<int>e[N];
 
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)e[i].clear();
	vector<edge>edges;
	
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		e[u].push_back(v);
		e[v].push_back(u);
		edges.push_back({u,v,w});
	}
	DSU dsu(n+1);
	sort(alls(edges),cmp);
	int ans=inf;
	int l,r;
	for(auto tmp:edges){
		auto [u,v,w]=tmp;
		if(!dsu.merge(u,v)){
			ans=w;l=u;r=v;
		}
	}
	vector<int>res;
	cout<<ans<<" ";
	bool flag=0;
	vector<bool>st(n+1,0);
	auto dfs=[&](auto self,int u,int fa)->void{
		
		
		if(u==r){
			res.push_back(u);
			flag=true;
			cout<<res.size()<<endl;
			for(auto x:res)cout<<x<<" ";
			return ;
		}
		if(st[u])return ;
		res.push_back(u);
		st[u]=true;
		for(auto v:e[u]){
			if(v==fa)continue;
			self(self,v,u);
			if(flag)return ;
			
		}
		if(flag==0)res.pop_back();
		return ;
	};
	dfs(dfs,l,r);
	cout<<endl;
}

Jiangly

在建图的时候，直接记录环上两个端点，但成环的边不建出来。在我的实现中还需要不断退环不合法的点，可以将递归函数的返回值定义为bool，只有成功的时候才加点进最终环上vector中，并且继续向上层递归函数返回true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
void solve() {
    int n, m;
    std::cin >> n >> m;
    
    std::vector<std::array<int, 3>> edges(m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        u--, v--;
        edges[i] = {w, u, v};
    }
    std::sort(edges.begin(), edges.end(), std::greater());
    
    int ans = 1E9;
    DSU dsu(n);
    int U, V;
    std::vector<std::vector<int>> adj(n);
    for (auto [w, u, v] : edges) {
        if (!dsu.merge(u, v)) {
            ans = w;
            U = u;
            V = v;
        } else {
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }
    
    std::vector<int> path;
    auto dfs = [&](auto self, int x, int p) -> bool {
        if (x == V) {
            path.push_back(x);
            return true;
        }
        for (auto y : adj[x]) {
            if (y == p) {
                continue;
            }
            if (self(self, y, x)) {
                path.push_back(x);
                return true;
            }
        }
        return false;
    };
    dfs(dfs, U, -1);
    
    std::cout << ans << " " << path.size() << "\n";
    reverse(path.begin(),path.end());
  
    for (auto x : path) {
        std::cout << x + 1 << " \n"[x == path.back()];
    }
}