题目链接:zoj 3820 Building Fire Stations
题目大意:给定一棵树,选取两个建立加油站,问说所有点距离加油站距离的最大值的最小值是多少,并且任意输出一种建立加油站的方式。
解题思路:二分距离判断,判断函数的复杂度是o(n),这样的复杂度应该是o(nlogn),即使常数系数偏大,但是居然跑了4.5s,也是醉了。
判断函数里面做了3次bfs,但是每次bfs节点最多遍历1次,首先任取一点做根建立一个树,找到深度最大的节点,以向上移动L(判断的ans)位置处的节点建立加油站,并以该点为根在建一棵树,这是第2次bfs,然后同样以最深的节点向上移动L次的节点建立加油站,判断这两个加油站使得所有节点距离加油站的值是否均小于等于L。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 200005;
const int INF = 0x3f3f3f3f;
int M, first[maxn], jump[maxn * 2], edge[maxn * 2];
int N, s, e, far[maxn], dis[maxn];
queue<int> que;
inline void add_edge(int u, int v) {
edge[M] = v;
jump[M] = first[u];
first[u] = M++;
}
void init () {
int l, r;
M = 0;
scanf("%d", &N);
memset(first, -1, sizeof(first));
for (int i = 1; i < N; i++) {
scanf("%d%d", &l, &r);
add_edge(l, r);
add_edge(r, l);
}
}
int bfs(int s) {
que.push(s);
dis[s] = far[s] = 0;
int u;
while (!que.empty()) {
u = que.front();
que.pop();
for (int i = first[u]; i + 1; i = jump[i]) {
int v = edge[i];
if (dis[v] > dis[u] + 1) {
far[v] = u;
dis[v] = dis[u] + 1;
que.push(v);
}
}
}
return u;
}
bool judge (int L) {
memset(dis, INF, sizeof(dis));
s = bfs(1);
for (int i = 0; i < L; i++) {
s = far[s];
if (far[s] == 0) {
e = s % N + 1;
return true;
}
}
memset(dis, INF, sizeof(dis));
e = bfs(s);
for (int i = 0; i < L; i++) {
if (far[e] == 0)
return true;
e = far[e];
}
if (e == s)
e = e % N + 1;
bfs(e);
for (int i = 1; i <= N; i++)
if (dis[i] > L)
return false;
return true;
}
void solve () {
if (N == 2) {
printf("0 1 2\n");
return ;
}
int l = 0, r = N;
while (l < r) {
int mid = (l + r) / 2;
if (judge(mid))
r = mid;
else
l = mid + 1;
}
judge(l);
printf("%d %d %d\n", l, s, e);
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
init();
solve();
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://weitch.iteye.com/blog/1006972
zoj_1004.cpp 求单词字母进出栈后能形成目标串的进出方案 广度优先搜索求解
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
zoj题目简单归类zoj题目简单归类zoj题目简单归类
深度搜索 回溯 int main { string s1 s2; while cin >> s1 >> s2 { count 0; cout << "[" << endl; if s1 length s2 length BackTrake s1 s2 ;... [更多]
浙江大学ZOJ源码题解,按照题目类型和难易分类。
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
zoj 3590 -3+1.md
其中有pku、hdu、zoj等各大oj的题目分类,pku的oj比较详细一点,按不同算法进行分类,均系从网上自行搜集的。
Problem Arrangement zoj 3777
ZOJ题目答案源码
浙大ACM网上的题目分类,以及部分题目的题解,包括题目,对于没联网的很适用,即使就有网的也很用的,里面有些题解很祥细……
一个非常非常非常非常实用的zoj结题代码
ZOJ1805代码
zoj 1003 c语言的,要写这么多描述吗。。
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够