洛谷 P5234 题解

$\text{Link}$

思路分析

显然，任何一条不是桥的边都不会对答案造成影响（因为在一个 E-DCC 中，任意删去一条边都不可能使图不连通）

所以我们可以对原图建立 dfs 搜索树并且求出桥，将所有树上非桥的边的边权都设为 $+\infty$

假设连了某一条边 $(u,v)$ ，使得答案为 $k$，则所有边权 $<k$ 的边都应该在简单路径 $(u,v)$ 上

考虑对答案二分，如果需要检查某个 $k$ 是否可能成为答案，我们只需要找到一条路径 $(u,v)$ 覆盖所有边权 $<k$ 的边即可

因此我们可以对每条边权 $<k$ 的边设为 $1$ 否则设为 $0$，然后用这个边权求一遍树的直径，只需要检查直径长度是否等于边权 $<k$ 的边的数量即可

时间复杂度 $\Theta(n\log T)$

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+1,INF=1e9;
struct node {
	int des,val,lst;
} edge[MAXN<<1],tr[MAXN<<1];
int low[MAXN],dfn[MAXN],head1[MAXN],head2[MAXN],cnt[MAXN],dp[MAXN],tot=0,ans=0,dfncnt,totedge=1,tottree=0,n,m;
inline void addedge(int u,int v,int w) {
	edge[++totedge]=(node){v,w,head1[u]};
	head1[u]=totedge;
}
inline void addtree(int u,int v,int w) {
	tr[++tottree]=(node){v,w,head2[u]};
	head2[u]=tottree;
}
inline void tarjan(int p,int uid) {
	low[p]=dfn[p]=++dfncnt;
	for(int i=head1[p];i;i=edge[i].lst) {
		int v=edge[i].des;
		if(!dfn[v]) {
			tarjan(v,i);
			low[p]=min(low[p],low[v]);
			if(low[v]<=dfn[p]) addtree(p,v,INF);
			else addtree(p,v,edge[i].val);
		} else if(i!=(uid^1)) low[p]=min(low[p],dfn[v]);
	}
	return ;
}
inline void dfs(int p,int l) {
	vector <int> vec;
	if(!head2[p]) dp[p]=cnt[p];
	for(int i=head2[p];i;i=tr[i].lst) {
		int v=tr[i].des;
		cnt[v]=cnt[p];
		if(tr[i].val<l) ++cnt[v],++tot;
		dfs(v,l);
		vec.push_back(dp[v]);
	}
	sort(vec.begin(),vec.end(),greater<int>());
	if(vec.size()>0) dp[p]=vec[0],ans=max(vec[0]-cnt[p],ans);
	if(vec.size()>1) ans=max(ans,vec[0]+vec[1]-cnt[p]*2);
}
inline bool check(int x) {
	memset(cnt,0,sizeof(cnt));
	memset(dp,0,sizeof(dp));
	ans=tot=0;
	dfs(1,x);
	return ans==tot;
}
signed main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		addedge(u,v,w);
		addedge(v,u,w);
	}
	tarjan(1,0);
	int l=0,r=INF,res=-1;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1,res=mid;
		else r=mid-1;
	}
	if(res==INF) res=-1;
	printf("%d\n",res);
	return 0;
}