The 2025 Shanghai Collegiate Programming Contest - J. 画圈（如何将白颜色的边的作用发挥到极致） · znzryb
## 思路讲解
```cpp
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](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**
### 最终算法
这个最终公式给了我们一个清晰的算法：
1. 读入 `N` 和 `M`。
1. 初始化一个并查集。
1. 遍历所有 `M` 条边：
- 如果是白边，就把白边计数器 `whiteCnt` 加一。
- 如果是黑边，就在并查集中 `unite` 这条边的两个端点。
1. 遍历完成后，统计并查集中有多少个独立的集合（也就是有多少个节点的父亲是它自己）。这个数量就是 `$K_B$`。
1. 代入公式 `whiteCnt - K_B + 1`，就是最终答案。
希望这个一步步的解释能帮助你彻底理解这道题的思路！
## AC代码
[https://codeforces.com/gym/105992/submission/328463103](https://codeforces.com/gym/105992/submission/328463103)
::: 源代码
```cpp
// 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
*/
```
:::
## 心路历程（WA，TLE，MLE……）