[BZOJ4331] [JSOI2012]越狱老虎桥

Posted on Edited on In

[BZOJ4331] [JSOI2012]越狱老虎桥

题意: 在任意加入一条边的情况下，求 割一条边使图不从1联通的最小割边的 最大值

首先根据题目的意思，可以下对这个无向图中 进行边双联通分量 缩点

建出一棵边双生成树，树边即为原图的割边，树边带权

割掉双联通分量内部的边显然没有意义，所以忽略掉他们，下文所提的均是树上节点和边

在不额外加边的情况下，而割掉树边会使子树内部的点断开

在加入边的情况下，若加入一条 \(1-u\) 的边，则形成了一个 \(1-u\) 的环，环是无法通过割开一条边断开的

而连接树上两个节点 \((u,v)\) 的情况，把图展开后，就会发现，就是把 \(u,v\) 路径上所有的点都缩进了同一个环

此时断掉环上的边显然不合法，而不在环上的边，只需要随便断掉一条，就能让一个点不连通

也就是说，答案是 (去掉某个点对 \((u,v)\) 路径上的所有边，剩下的边中最小值) 的最大值

设答案为 \(ans\)

这个问题实际上等价于所有的 \(e\in E,w(e)\leq ans\) 的边无法被一条路径完全覆盖

做法1:

考虑二分答案，把每条 \(e\in E,w(e)\leq ans\) 的边的权值设为1，求出直径长度判断是否可以用一条路径完全覆盖即可

复杂度为 \(O(n\log n)\)

做法2:

实际上这个问题就是 (选择了合法的3条边中边权的最大值) 的最小值

对于当前节点 \(u\) ，实际合法情况有

1.选择了一条祖先的边，和2条儿子岔开的边

2.选择了3条垂下的岔开的边，这个合并时比较诡异可以看代码

\(\text{dp}\) 维护即可，复杂度为 \(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,const T &b){ ((a>b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=5e5+10,INF=1e9+10;

int n,m;
struct Edge{
	int to,nxt,w;
} e[N*6];
int head[N],ecnt;
void AddEdge(int u,int v,int w) {
	e[++ecnt]=(Edge){v,head[u],w};
	head[u]=ecnt;
}
#define erep(u,i) for(int i=head[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to)

int low[N],t[N],id[N],scc,dfn;
int stk[N],top;
void dfs(int u,int f) {
	low[u]=t[u]=++dfn;
	stk[++top]=u;
	erep(u,i) if(v!=f) {
		if(!t[v]) dfs(v,u),cmin(low[u],low[v]);
		else cmin(low[u],t[v]);
	}
	if(low[u]==t[u]){
		int v; ++scc;
		do v=stk[top--],id[v]=scc;
		while(v!=u);
	}
}

int head2[N];
void AddEdge2(int u,int v,int w) {
	e[++ecnt]=(Edge){v,head2[u],w};
	head2[u]=ecnt;
}
#define erep2(u,i) for(int i=head2[u],v=e[i].to,w=e[i].w;i;i=e[i].nxt,v=e[i].to,w=e[i].w)

int ans=INF;
int dp[N][4],tmp[4],g[N];

void dfs1(int u,int f) {
	dp[u][0]=0,dp[u][1]=dp[u][2]=dp[u][3]=INF;
	erep2(u,i) if(v!=f) {
		g[v]=min(g[u],w),dfs1(v,u);
		memset(tmp,63,sizeof tmp);
		rep(j,0,3) {
			cmin(tmp[j],dp[u][j]);
			if(j<3) cmin(tmp[j+1],max(dp[u][j],w));
			rep(k,0,3-j) cmin(tmp[j+k],max(dp[u][j],dp[v][k]));
		}
		rep(j,0,3) dp[u][j]=tmp[j];
	}
	cmin(ans,dp[u][3]);
	cmin(ans,max(g[u],dp[u][2]));
}


int main(){
	n=rd(),m=rd();
	rep(i,1,m) {
		int u=rd(),v=rd(),w=rd();
		AddEdge(u,v,w),AddEdge(v,u,w);
	}
	dfs(1,0);
	rep(u,1,n) erep(u,i) if(id[u]!=id[v]) AddEdge2(id[u],id[v],e[i].w);
	g[id[1]]=INF,dfs1(id[1],0);
	printf("%d\n",ans==INF?-1:ans);
}