题目大意

给出一张图，给出q对点，求这两个点间权值最小边最大的路径，输出这个最小边权。

题解

我们先一条一条边建图。当建立的边使得图中形成环时，因为环中的每个节点只考虑是否连通和瓶颈大小，要想互相连通只要一条路就够了，而只有环上的最小边和次小边可能是这条路的瓶颈，且这条路的瓶颈肯定越大越好。故根据贪心，我们可以直接把环中的权值最小边删去。

所以我们就维护一个LCT来随时删边增边，还要用到拆边等方法来统计路径上的值吗？能AC，但太复杂了！

我们从整体考虑，第一段叙述中，每次遇到一个环，其值为S。由于去掉的是最小边，边权w，所以剩余的路径上的边权和S-w是最大的。所以这就是一个最大生成树。所以我们就用Kruskal算法求出最大生成树，再由树上倍增求解即可。注意Kruskal处理的是单向边而不是无向图，所以先Kruskal，再建图。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdarg>

using namespace std;

const int MAX_NODE = 10010, MAX_EDGE = 50010 * 2, MAX_LOG = 20, INF = 0x3f3f3f3f;

struct Node;

struct Edge;

struct Node {

	Edge *Head;

	Node *Elder[MAX_LOG];

	Node *Root;

	int MinVal[MAX_LOG];

	int Depth;

	Node *Father;

}_nodes[MAX_NODE], *CurRoot;

int _vCount;

struct Edge {

	Node *From, *To;

	Edge *Next;

	int Weight;

	Edge(Node *from, Node *to, int w):From(from),To(to),Weight(w),Next(NULL){}

	Edge() {}

}_edges[MAX_NODE * 2], tempEdges[MAX_EDGE];

int _eCount, tempeCount;

Edge *NewEdge() {

	return _edges + (++_eCount);

}

Edge *AddEdge(Node *from, Node *to, int w) {

	Edge *e = NewEdge();

	e->To = to;

	e->From = from;

	e->Weight = w;

	e->Next = from->Head;

	from->Head = e;

	return e;

}

void Build(int uId, int vId, int w) {

	tempEdges[++tempeCount] = Edge(_nodes + uId, _nodes + vId, w);

}

int Log2(int x) {

	int ans = 0;

	while (x >>= 1)

		ans++;

	return ans;

}

void Dfs(Node *cur, Edge *FromFa) {

	cur->Root = CurRoot;

	if (FromFa == NULL) {

		cur->Depth = 1;

		cur->MinVal[0] = INF;

	}

	else {

		cur->Elder[0] = FromFa->From;

		cur->Depth = cur->Elder[0]->Depth + 1;

		cur->MinVal[0] = FromFa->Weight;

		for (int i = 1; cur->Elder[i - 1]->Elder[i - 1]; i++) {

			cur->Elder[i] = cur->Elder[i - 1]->Elder[i - 1];

			cur->MinVal[i] = min(cur->MinVal[i - 1], cur->Elder[i - 1]->MinVal[i - 1]);

		}

	}

	for (Edge *e = cur->Head; e; e = e->Next)

		if (e->To != cur->Elder[0])

			Dfs(e->To, e);

}

void DfsStart() {

	for (int i = 1; i <= _vCount; i++) {

		if (!_nodes[i].Depth) {

			CurRoot = _nodes + i;

			Dfs(CurRoot, NULL);

		}

	}

}

int Lca(Node *deep, Node *high) {

	if (deep->Root != high->Root)

		return -1;

	int ans = INF;

	if (deep->Depth < high->Depth)

		swap(deep, high);

	int len = deep->Depth - high->Depth;

	for (int k = 0; len; k++) {

		if ((1 << k)&len) {

			ans = min(ans, deep->MinVal[k]);

			deep = deep->Elder[k];

			len -= (1 << k);

		}

	}

	if (deep == high)

		return ans;

	for (int k = Log2(deep->Depth); k >= 0; k--) {

		if (deep->Elder[k] != high->Elder[k]) {

			ans = min(ans, deep->MinVal[k]);

			ans = min(ans, high->MinVal[k]);

			deep = deep->Elder[k];

			high = high->Elder[k];

		}

	}

	ans = min(ans, deep->MinVal[0]);

	ans = min(ans, high->MinVal[0]);

	return ans;

}

bool CmpEdge(Edge a, Edge b) {

	return a.Weight > b.Weight;

}

Node *FindFather(Node *cur) {

	return cur == cur->Father ? cur : cur->Father = FindFather(cur->Father);

}

void Join(Node *root1, Node *root2) {

	root1->Father = root2;

}

void Kruskal() {

	sort(tempEdges + 1, tempEdges + tempeCount + 1, CmpEdge);

	for (int i = 1; i <= _vCount; i++)

		_nodes[i].Father = _nodes + i;

	for (int i = 1; i <= tempeCount; i++) {

		Edge e = tempEdges[i];

		Node *root1 = FindFather(e.From), *root2 = FindFather(e.To);

		if (root1 != root2) {

			AddEdge(e.From, e.To, e.Weight);

			AddEdge(e.To, e.From, e.Weight);

			Join(root1, root2);

		}

	}

}

int main() {

	int totEdge;

	scanf("%d%d", &_vCount, &totEdge);

	for (int i = 1; i <= totEdge; i++) {

		int u, v, w;

		scanf("%d%d%d", &u, &v, &w);

		Build(u, v, w);

	}

	Kruskal();

	DfsStart();

	int queryCnt;

	scanf("%d", &queryCnt);

	while (queryCnt--) {

		int u, v;

		scanf("%d%d", &u, &v);

		printf("%d\n", Lca(_nodes + u, _nodes + v));

	}

	return 0;

}

巴特西

luogu1967 货车运输最大瓶颈生成树

题目大意

题解

最新文章

热门文章

巴特西

luogu1967 货车运输 最大瓶颈生成树

题目大意

题解

最新文章

热门文章

luogu1967 货车运输最大瓶颈生成树