BZOJ 3732 Network 最小瓶颈路

全栈程序员-站长 • 2022年3月3日上午6:00 • 未分类 • 阅读 33

大家好，又见面了，我是全栈君。

题目大意：给出一个无向边，非常多询问，问x，y两地之间的最长路最短是多少。

思路：乍一看好像是二分啊。

的确这个题二分能够做。可是时间会慢非常多，有的题直接就T掉（NOIP2013货车运输）。

事实上这个题的模型就是最小瓶颈路模型。

解法就是把无向图变成一个最小生成树，然后两点之间的最长路就是满足题意的答案。

CODE：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 15010
#define INF 0x7f7f7f7f
using namespace std;

struct Complex{
	int x,y,len;

	bool operator <(const Complex &a)const {
		return len < a.len;
	}
	void Read() {
		scanf("%d%d%d",&x,&y,&len);
	}
}edge[MAX << 2];

int points,edges,asks;
int head[MAX],total;
int next[MAX << 1],length[MAX << 1],aim[MAX << 1];

int fa[MAX];

int deep[MAX];
int father[MAX][20],min_length[MAX][20];

void Pretreatment();
int Find(int x);

inline void Add(int x,int y,int len);

void DFS(int x,int last);
void SparseTable();

int GetLCA(int x,int y);

int main()
{
	cin >> points >> edges >> asks;
	Pretreatment();
	for(int i = 1;i <= edges; ++i)
		edge[i].Read();
	sort(edge + 1,edge + edges + 1);
	for(int i = 1;i <= edges; ++i) {
		int fx = Find(edge[i].x);
		int fy = Find(edge[i].y);
		if(fx != fy) {
			Add(edge[i].x,edge[i].y,edge[i].len);
			Add(edge[i].y,edge[i].x,edge[i].len);
			fa[fx] = fy;
		}
	}
	DFS(1,0);
	SparseTable();
	for(int x,y,i = 1;i <= asks; ++i) {
		scanf("%d%d",&x,&y);
		printf("%d\n",GetLCA(x,y));
	}
	return 0;
}

void Pretreatment()
{
	for(int i = 1;i <= points; ++i)
		fa[i] = i;
}

int Find(int x)
{
	if(fa[x] == x)	return x;
	return fa[x] = Find(fa[x]);
}

inline void Add(int x,int y,int len)
{
	next[++total] = head[x];
	aim[total] = y;
	length[total] = len;
	head[x] = total; 
}

void DFS(int x,int last)
{
	deep[x] = deep[last] + 1;
	for(int i = head[x];i;i = next[i]) {
		if(aim[i] == last)	continue;
		father[aim[i]][0] = x;
		min_length[aim[i]][0] = length[i];
		DFS(aim[i],x);
	}
}

void SparseTable()
{
	for(int j = 1;j < 20; ++j)
		for(int i = 1;i <= points; ++i) {
			father[i][j] = father[father[i][j - 1]][j - 1];
			min_length[i][j] = max(min_length[i][j - 1],min_length[father[i][j - 1]][j - 1]);
		}
}

int GetLCA(int x,int y)
{
	int re = 0;
	if(deep[x] < deep[y])	swap(x,y);
	for(int i = 19;i >= 0; --i)
		if(deep[father[x][i]] >= deep[y]) {
			re = max(re,min_length[x][i]);
			x = father[x][i];
		}
	if(x == y)	return re;
	for(int i = 19;i >= 0; --i)
		if(father[x][i] != father[y][i]) {
			re = max(re,min_length[x][i]);
			re = max(re,min_length[y][i]);
			x = father[x][i];
			y = father[y][i];
		}
	re = max(re,min_length[x][0]);
	re = max(re,min_length[y][0]);
	return re;
}

转载于:https://www.cnblogs.com/yutingliuyl/p/6800033.html

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/108523.html原文链接：https://javaforall.net