首页 > 代码库 > ZOJ 3820 Building Fire Stations 贪心+树的直径
ZOJ 3820 Building Fire Stations 贪心+树的直径
不知道为什么是对的,但是举不出反例,比赛的时候队友提出找树的直径,不过我没敢写,真是可惜。
具体做法就是先找到原树的直径,然后删去最中间的一条边,变为两个子树,分别球两颗子树的直径中点,便是答案了。
#include <cstdio>#include <cstring>#include <algorithm>#include <queue>#include <stack>#include <map>#include <set>#include <climits>#include <iostream>#include <string>using namespace std; #define MP make_pair#define PB push_backtypedef long long LL;typedef unsigned long long ULL;typedef vector<int> VI;typedef pair<int, int> PII;typedef pair<double, double> PDD;const int INF = INT_MAX / 3;const double eps = 1e-8;const LL LINF = 1e17;const double DINF = 1e60;const int maxn = 2e5 + 10;int head[maxn], nxt[maxn << 1], u[maxn << 1], v[maxn << 1], ecnt;int n, dist[maxn], pre[maxn], path[maxn], id[maxn];bool vis[maxn], del[maxn << 1];void adde(int uu, int vv) { u[ecnt] = uu; v[ecnt] = vv; nxt[ecnt] = head[uu]; head[uu] = ecnt++;}//bfs 参数为起点, 返回终点(离起点最远的一个点)int bfs(int str, int col) { memset(vis, 0, sizeof(vis)); vis[str] = true; dist[str] = 0; pre[str] = -1; queue<int> q; q.push(str); int now = 0; while(!q.empty()) { now = q.front(); q.pop(); id[now] = col; for(int i = head[now]; ~i; i = nxt[i]) if(!del[i]) { if(!vis[v[i]]) { pre[v[i]] = now; dist[v[i]] = dist[now] + 1; q.push(v[i]); vis[v[i]] = true; } } } return now;}void solve() { //第一遍, 求树的直径 int s, t, len = 0, du, dv; s = bfs(1, -1); t = bfs(s, -1); for(int i = t; ~i; i = pre[i]) { path[len++] = i; } //删除最中间的边 for(int i = t, j = 0; ~i; i = pre[i], j++) { if((j + 1) == len / 2) { du = i; dv = pre[i]; break; } } for(int i = 0; i < ecnt; i++) { if((u[i] == du && v[i] == dv) || (u[i] == dv && v[i] == du)) { del[i] = true; } } //对两边的子树分别求直径 int maxlen = 0, p[2], pcnt = 0; for(int i = 1; i <= n; i++) if(id[i] == -1) { s = bfs(i, pcnt); t = bfs(s, pcnt); len = 0; for(int j = t; ~j; j = pre[j]) path[len++] = j; for(int j = t, k = 0; ~j; j = pre[j], k++) if((k + 1) == (len + 1) / 2) { p[pcnt++] = j; break; } maxlen = max(maxlen, len / 2); } printf("%d %d %d\n", maxlen, p[0], p[1]);}int main() { int T; scanf("%d", &T); while(T--) { ecnt = 0; scanf("%d", &n); memset(head, -1, sizeof(head)); memset(del, 0, sizeof(del)); for(int i = 0; i < n - 1; i++) { int a, b; scanf("%d%d", &a, &b); adde(a, b); adde(b, a); } solve(); } return 0;}
ZOJ 3820 Building Fire Stations 贪心+树的直径
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。