标签：ref   min   include   begin   getch   lang   最大值   false   put   

题目链接

Solution [JSOI2012]越狱老虎桥

题目大意：给定一张带权无向图，你可以任意添加一条边，求权值最小的割边的最大值

Tarjan，贪心

分析：

我们先考虑是一棵树的情况，显然每一条边都是割边，我们添加一条边可以产生一个简单环，那么环上的所有边就都不是割边了

考虑贪心，我们将边权从小到大排序，逐次加入，如果当前边无法和之前的所有边构成一条链，那么当前边权就是答案（也就是贪心的尽量将最小的几条割边丢进一个环里面）

对于普通无向图，缩点之后用同样的方法处理

如何判断能否构成一条链，可以记录一下链的起点终点，结合父子关系 / \(\text{LCA}\)讨论一下即可，详见代码

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 5e5 + 100;
inline int read(){
	int x = 0;char c = getchar();
	while(!isdigit(c))c = getchar();
	while(isdigit(c))x = x * 10 + c - ‘0‘,c = getchar();
	return x;
}
struct edge{
	int u,v,d;
	bool operator  dfn[u])iscut[i] = iscut[i ^ 1] = 1;
		}else if((i ^ 1) != faz)low[u] = min(low[u],dfn[v]);
	}
}
int col[maxn],col_tot;
inline void bfs(int s,int c){
	queue q;
	q.push(s);
	while(!q.empty()){
		int u = q.front();q.pop();
		col[u] = c;
		for(int i = head[u];i;i = nxt[i]){
			int v = edges[i].v;
			if(iscut[i] || col[v])continue;
			q.push(v);
		}
	}
}
vector G[maxn];
vector vec;
inline void addedge(int u,int v){G[u].push_back(v);}
const int maxdep = 26;
int dep[maxn],faz[maxn][maxdep + 1],rt,fir,lst;
inline void dfs(int u){
	for(int i = 1;i = 0;i--)
		if(dep[faz[x][i]] >= dep[y])x = faz[x][i];
	return x == y;
}
inline int lca(int x,int y){
	if(dep[x] = 0;i--)
		if(dep[faz[x][i]] >= dep[y])x = faz[x][i];
	if(x == y)return x;
	for(int i = maxdep;i >= 0;i--)
		if(faz[x][i] != faz[y][i])x = faz[x][i],y = faz[y][i];
	return faz[x][0];
}
int n,m;
int main(){
	n = read(),m = read();
	for(int u,v,d,i = 1;i  dep[e.v])swap(e.u,e.v);
	for(auto e : vec){
		if(!fir){
			fir = e.u;
			lst = e.v;
			continue;
		}
		if((isson(e.u,fir) || e.u == fir) && !isson(lca(lst,e.u),fir))fir = e.v;
		else if((isson(e.u,lst) || e.u == lst) && !isson(lca(fir,e.u),lst))lst = e.v;
		else return printf("%d\n",e.d),0;
	}
	return 0;
}

题解 P5234 【[JSOI2012]越狱老虎桥】

标签：ref   min   include   begin   getch   lang   最大值   false   put   

原文地址：https://www.cnblogs.com/colazcy/p/13768489.html