The 2025 Shanghai Collegiate Programming Contest - J. 画圈（如何将白颜色的边的作用发挥到极致）

思路讲解

FOR(i,1,M){
	ll u,v,w;cin>>u>>v>>w;
	E[i]={u,v,w};
	if(w==1){
		merge(u,v);
	}
}
ll VB=0;
FOR(i,1,N){
	if(fa[i]==i) ++VB;	// 黑图联通块数量。
}
ll ans=0,rem=0;
FOR(i,1,M){
	auto [u,v,w]=E[i];
	if(w==0){
		if(find(u)==find(v)){	// 这个白边的两个端点在黑图上是联通的
			++ans;	// 涂这些白边只需要消耗一个，就可以贡献一个答案
		}else{
			++rem;	// 剩余白边
		}
	}
}
ans+=max(0ll,rem-VB+1);

https://gemini.google.com/gem/coding-partner/f12365cf9d028877

好的，我们一起来用中文梳理一下这道题的思路。我会试着一步步引导你，而不是直接告诉你答案。

第一步：思考问题的本质

我们想让操作次数尽可能多。每次操作都需要一个“引子”：一个包含至少一条白边的环。操作完成后，这个环里所有的白边都会变成黑边。

一个很自然的想法是：我们的操作次数，会不会受到白边总数的限制？

是的，每次操作我们至少“消耗”掉了一条白边（它从白色变成了黑色，之后就不能再作为“引子”了）。所以，操作次数的上限，就是初始状态下白边的总数。

那么，是不是每条白边都能贡献一次操作呢？

第二步：寻找最“划算”的操作

为了让操作次数最多，我们应该让每次操作都尽可能“划算”。最划算的操作是什么样的？就是我们只用一条白边作为“引子”，去把一个环染黑。

思考一下，什么样的环正好只有一条白边，其余都是黑边？

… 答案是：当一条白边 (u, v) 的两个端点 u 和 v，已经能通过一条纯黑边路径连接起来时。这时，这条白边和这条纯黑边路径就构成了一个完美的环，里面只有一条白边。

我们可以把所有这种“划算”的白边都找出来。对于每一条这样的白边，我们都可以进行一次独立的操作。

如何找到它们？

我们可以先把图中所有的黑边建成一个图。然后遍历每一条白边 (u, v)，看看在只考虑黑边的前提下，u 和 v 是否已经连通了。如果连通，那这条白边就是一条“划算”的边，可以贡献一次操作。

这个“判断是否连通”的任务，听起来是不是很熟悉？对，这正是并查集 (DSU) 的拿手好戏。

第三步：处理剩下的白边

好，现在我们已经把所有“划算”的白边都用掉了。剩下的白边是什么样的？

它们连接的都是原本在黑边图里不连通的点。我们可以把黑边图中每一个连通块想象成一个“大岛屿”（或者叫“超级节点”）。那么，这些剩下的白边，就成了连接这些岛屿的“桥梁”。

现在，我们的图变成了这个样子：有若干个黑色的岛屿，以及连接它们的白色桥梁。

因为题目保证原图是连通的，所以这些岛屿和桥梁最终也会构成一个连通的结构。

在这个由“岛屿”和“桥梁”组成的新图里，我们还能找到环吗？

当然能！如果这些桥梁的数量足够多，多到在这个新图里形成了环，那我们就可以继续操作。

例如，从岛屿A出发，经过白色桥梁1到达岛屿B，再经过白色桥梁2到达岛屿C，最后经过白色桥梁3又回到了岛屿A。这就构成了一个大环！这个环里的边，要么是白色的桥梁，要么是岛屿内部的黑色路径。它肯定包含白边，所以我们可以对它进行一次操作。

第四步：计算新图里的操作次数

在一个连通图里，有多少“多余”的边可以形成环呢？

有一个经典的图论公式：对于一个有 V 个点、E 条边的连通图，它的“环度”（也就是基本环的数量）是 E - V + 1。这也就是我们能从这个结构中挤出的操作次数。

在我们的“岛屿和桥梁”新图里：

V 是多少？就是黑色连通块的数量，我们称之为 $K_B$ 。
E 是多少？就是剩下的白边（桥梁）的数量。

所以，从这些剩下的白边中，我们还能进行 $E_{剩余白边} - K_B + 1$ 次操作。

第五步：整合答案

现在把两部分的操作次数加起来：

总操作数 = (第二步中“划算”的白边数) + (第四步中“桥梁”构成的操作数)

总操作数 = $|W_s| + (|W_d| - K_B + 1)$

（这里 $|W_s|$ 是划算的白边数， $|W_d|$ 是桥梁白边数）

因为白边总数 $|W| = |W_s| + |W_d|$ ，所以上面这个公式可以简化成一个非常优美的形式：

总操作数 = (总白边数 ∣W∣) - (黑色连通块数 KB) + 1

最终算法

这个最终公式给了我们一个清晰的算法：

读入 N 和 M。
初始化一个并查集。
遍历所有 M 条边：

如果是白边，就把白边计数器 whiteCnt 加一。
如果是黑边，就在并查集中 unite 这条边的两个端点。

遍历完成后，统计并查集中有多少个独立的集合（也就是有多少个节点的父亲是它自己）。这个数量就是 $K_B$ 。
代入公式 whiteCnt - K_B + 1，就是最终答案。

希望这个一步步的解释能帮助你彻底理解这道题的思路！

AC代码

https://codeforces.com/gym/105992/submission/328463103

源代码

// Problem: J. 画圈
// Contest: Codeforces - The 2025 Shanghai Collegiate Programming Contest
// URL: https://codeforces.com/gym/105992/problem/J
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll MAXM=(ll)1e6+10;constexpr ll MAXV=(ll)1e6+10;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;const double pi=acos(-1.0);

ll N,M,Q,X,K,T,lT;
/*

*/
ll fa[MAXN];
inline void init(){
	FOR(i,1,N){
		fa[i]=i;
	}
}
int find(ll x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(ll a,ll b){
	fa[find(a)]=find(b);
}
inline void solve(){
	cin>>N>>M;
	init();
	vector<arr3> E(M+5);
	FOR(i,1,M){
		ll u,v,w;cin>>u>>v>>w;
		E[i]={u,v,w};
		if(w==1){
			merge(u,v);
		}
	}
	ll VB=0;
	FOR(i,1,N){
		if(fa[i]==i) ++VB;
	}
	ll ans=0,rem=0;
	FOR(i,1,M){
		auto [u,v,w]=E[i];
		if(w==0){
			if(find(u)==find(v)){
				++ans;
			}else{
				++rem;
			}
		}
	}
#ifdef LOCAL
	debug(ans);
#endif
	ans+=max(0ll,rem-VB+1);
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--)
		solve();
	return 0;
}
/*
AC
https://codeforces.com/gym/105992/submission/328463103
*/

Znzryb's Blog