题解：P13548 [OOI 2022] Air Reform
PizzaYY
·
·
题解
思路
神仙题。
首先发现 u,v 两点间的路径边权最大值的最小值，其实就是最小生成树上 u,v 的路径边权最大值。所以我们现在考虑求 G 的补图 G' 的最小生成树。
考虑在图 G 上做 Kruskal 的过程。加入一条最小生成树上的边 (u,v,w) 时，补图中 u 那一侧的点（即当前在原图中和 u 联通的点）会形成若干联通块 S_u，v 那一侧的点会形成若干联通块 S_v。给新图中每个联通块一个编号 x，那么这个联通块中的点为 T_x。
枚举 S_u 中的联通块 x，枚举 S_v 中的联通块 y，那么这两个联通块能合并当且仅当对于 a\in T_x,b\in T_y，存在 (a,b) 在原图中没有这条边。
暴力枚举这个 a,b，找到合法的相当于在补图最小生成树中加入 (a,b,w)，且将 x,y 这两个联通块合并起来。
具体的，我们在合并的过程中先只管 x 会将 S_v 内部那些联通块合并起来，枚举完所有的 x 后再将 S_u 中的联通块和 S_v 合并。
对于 T，合并两个联通块只会让 T_x,T_y 合并（启发式合并维护）。而我们在最后将 S_u 合并到 S_v，所以我们需要 S_u 中每个联通块和 S_v 中的哪个联通块合并，由于 S_v 上会合并很多次，所以需要并查集。
对于 S，记录当前这个 x 与 S_v 中哪些联通块合并为 vec，显然 vec 中的联通块在 S_v 应该只剩下一个。若 x 不与其中任何一个发生合并，就在枚举完 S_u 中的所有元素后在 S_v 中加入 x。
分析一下复杂度，忽略启发式合并，瓶颈在于枚举 (a,b)。分两个部分：
- 当我枚举到一条不存在的边时可以直接退出枚举的过程。每次合并都是有效的，最多合并 n 次，所以这部分时间复杂度是 O(n) 的。
- 若我枚举到一条存在的边，而这两个联通块以后一定会在同侧出现，不会再枚举到这条边。所以每条出现过的边只会被枚举一次，这部分时间复杂度是 O(m) 的。
然后就只剩下一个树上路径最大值，这个十分简单，可以用你喜欢的数据结构处理（下面给出的代码中使用倍增）。
时间复杂度 $O(n\log n)$。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n,m,U[N],V[N],f[N],F[N];
int find(int x)
{
if(f[x]==x) return x;
return f[x] = find(f[x]);
}
int find2(int x)
{
if(F[x]==x) return x;
return F[x] = find2(F[x]);
}
vector<int> vec[N],vec2[N];
struct node{
int u,v,w;
inline friend bool operator < (node x,node y){return x.w<y.w;}
}e[N];
map<pair<int,int>,int> mp;
int cnt,head[N],nxt[N<<1],to[N<<1],g[N<<1];
inline void add(int u,int v,int w)
{
nxt[++cnt] = head[u];
head[u] = cnt;
to[cnt] = v,g[cnt] = w;
}
int fa[N][20],mx[N][20],dep[N];
void dfs(int u,int Fa)
{
dep[u] = dep[Fa]+1;
for(int i = head[u];i;i = nxt[i])
{
int v = to[i],w = g[i];
if(v==Fa) continue;
dfs(v,u);
fa[v][0] = u,mx[v][0] = w;
}
}
inline int ask(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
int res = 0;
for(int i = 19;~i;i--)
if(dep[fa[x][i]]>=dep[y])
res = max(res,mx[x][i]),x = fa[x][i];
if(x==y) return res;
for(int i = 19;~i;i--)
if(fa[x][i]!=fa[y][i])
res = max({res,mx[x][i],mx[y][i]}),x = fa[x][i],y = fa[y][i];
return max({res,mx[x][0],mx[y][0]});
}
inline void solve()
{
cin>>n>>m;
mp.clear();
for(int i = 1;i<=m;i++)
cin>>e[i].u>>e[i].v>>e[i].w,mp[{e[i].u,e[i].v}] = mp[{e[i].v,e[i].u}] = i,U[i] = e[i].u,V[i] = e[i].v;
for(int i = 1;i<=n;i++) F[i] = f[i] = i,head[i] = 0;
cnt = 0;
for(int i = 1;i<=n;i++)
{
vec[i].clear(),vec2[i].clear();
vec[i].push_back(i),vec2[i].push_back(i);
}
sort(e+1,e+m+1);
for(int i = 1;i<=m;i++)
{
int u = find(e[i].u),v = find(e[i].v),w = e[i].w;
if(u==v) continue;
for(auto i:vec[u])
{
int fir = 0;
vector<int> tmp;
for(auto j:vec[v])
{
bool fl = 0;
for(auto x:vec2[i])
{
for(auto y:vec2[j])
if(!mp.count({x,y}))
{
add(x,y,w);
add(y,x,w);
fl = 1;
break;
}
if(fl) break;
}
if(fl)
{
if(!fir) tmp.push_back(F[i] = fir = j);//只留下第一个
else
{
F[j] = fir;
if(vec2[j].size()>vec2[fir].size()) vec2[fir].swap(vec2[j]);
for(auto k:vec2[j]) vec2[fir].push_back(k);
vec2[j].clear();
}
}
else tmp.push_back(j);
}
vec[v].swap(tmp);
}
for(auto i:vec[u])
if(find2(i)==i) vec[v].push_back(i);
else
{
int x = find2(i);
if(vec2[i].size()>vec2[x].size()) vec2[x].swap(vec2[i]);
for(auto k:vec2[i]) vec2[x].push_back(k);
vec2[i].clear();
}
f[u] = v;
}
dfs(1,0);
for(int j = 1;j<20;j++)
for(int i = 1;i<=n;i++)
fa[i][j] = fa[fa[i][j-1]][j-1],mx[i][j] = max(mx[i][j-1],mx[fa[i][j-1]][j-1]);
for(int i = 1;i<=m;i++)
cout<<ask(U[i],V[i])<<' ';
cout<<'\n';
}
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T,subid;cin>>T>>subid;
while(T--) solve();
return 0;
}
```