专栏文章

题解：P13548 [OOI 2022] Air Reform

PPizzaYY
P13548题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minlto2d
此快照首次捕获于
2025/12/02 04:31
3 个月前
此快照最后确认于
2025/12/02 04:31
3 个月前
查看原文

思路

神仙题。
首先发现 u,vu,v 两点间的路径边权最大值的最小值，其实就是最小生成树上 u,vu,v 的路径边权最大值。所以我们现在考虑求 GG 的补图 G′G' 的最小生成树。
考虑在图 GG 上做 Kruskal 的过程。加入一条最小生成树上的边 (u,v,w)(u,v,w) 时，补图中 uu 那一侧的点（即当前在原图中和 uu 联通的点）会形成若干联通块 SuS_u，vv 那一侧的点会形成若干联通块 SvS_v。给新图中每个联通块一个编号 xx，那么这个联通块中的点为 TxT_x。
枚举 SuS_u 中的联通块 xx，枚举 SvS_v 中的联通块 yy，那么这两个联通块能合并当且仅当对于 a∈Tx,b∈Tya\in T_x,b\in T_y，存在 (a,b)(a,b) 在原图中没有这条边。
暴力枚举这个 a,ba,b，找到合法的相当于在补图最小生成树中加入 (a,b,w)(a,b,w)，且将 x,yx,y 这两个联通块合并起来。
具体的，我们在合并的过程中先只管 xx 会将 SvS_v 内部那些联通块合并起来，枚举完所有的 xx 后再将 SuS_u 中的联通块和 SvS_v 合并。
对于 TT，合并两个联通块只会让 Tx,TyT_x,T_y 合并（启发式合并维护）。而我们在最后将 SuS_u 合并到 SvS_v，所以我们需要 SuS_u 中每个联通块和 SvS_v 中的哪个联通块合并，由于 SvS_v 上会合并很多次，所以需要并查集。
对于 SS，记录当前这个 xx 与 SvS_v 中哪些联通块合并为 vecvec，显然 vecvec 中的联通块在 SvS_v 应该只剩下一个。若 xx 不与其中任何一个发生合并，就在枚举完 SuS_u 中的所有元素后在 SvS_v 中加入 xx。
分析一下复杂度，忽略启发式合并，瓶颈在于枚举 (a,b)(a,b)。分两个部分：
  1. 当我枚举到一条不存在的边时可以直接退出枚举的过程。每次合并都是有效的，最多合并 nn 次，所以这部分时间复杂度是 O(n)O(n) 的。
  2. 若我枚举到一条存在的边，而这两个联通块以后一定会在同侧出现，不会再枚举到这条边。所以每条出现过的边只会被枚举一次，这部分时间复杂度是 O(m)O(m) 的。
n,mn,m 同阶，则建立补图最小生成树复杂度为 O(nlog⁡n)O(n\log n)。
然后就只剩下一个树上路径最大值，这个十分简单，可以用你喜欢的数据结构处理（下面给出的代码中使用倍增）。
时间复杂度 O(nlog⁡n)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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...