国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > bzoj 1023 仙人掌图

bzoj 1023 仙人掌图

来源:程序员人生   发布时间:2015-03-10 08:29:06 阅读次数:2954次

Description

求1个神仙掌图的直径

Solution

神仙掌图有个性质,1条边要末是割边要末就是在环内,那末我们可以对它进行Dp辣!

f[u]u

如果u?v是桥的话转移就是ans=max(ans,f[u]+f[v]+1)f[u]=max(f[u],f[v]+1),由于当前f[u]都是由它的孩子更新来的

如果是环的话,变环为链,用单调队列dp出ans,然后用环上的f值更新f[u]的值就能够了,具体实现见代码

Code

#include <bits/stdc++.h> using namespace std; const int N = 100005, M = N << 1; int ans, ind, tot, cnt, fa[N], cir[N << 1], to[M << 1], nxt[M << 1], head[N], dfn[N], low[N], f[N]; inline int read(int &t) { int f = 1;char c; while (c = getchar(), c < '0' || c > '9') if (c == '-') f = -1; t = c - '0'; while (c = getchar(), c >= '0' && c <= '9') t = t * 10 + c - '0'; t *= f; } struct data { int p, w; }q[N]; void add(int u, int v) { to[tot] = v, nxt[tot] = head[u], head[u] = tot++; to[tot] = u, nxt[tot] = head[v], head[v] = tot++; } void gao() { int h = 1, r = 1; for (int i = 1; i <= cnt; ++i) cir[cnt + i] = cir[i]; for (int i = 1; i <= (cnt << 1); ++i) { while (h < r && i - q[h].p > cnt / 2) ++h; while (h < r && q[r].w <= f[cir[i]] - i) --r; q[++r].p = i, q[r].w = f[cir[i]] - i; ans = max(ans, f[cir[i]] + i + q[h].w); } } void dfs(int u) { low[u] = dfn[u] = ++ind; for (int i = head[u], v; ~i; i = nxt[i]) { v = to[i]; if (fa[v] != 0 && v != fa[u]) low[u] = min(low[u], dfn[v]); if (fa[v] == 0) { fa[v] = u; dfs(v); low[u] = min(low[u], low[v]); } } for (int i = head[u], v; ~i; i = nxt[i]) { v = to[i]; if (fa[v] == u && low[v] > dfn[u]) { //bridge ans = max(ans, f[u] + f[v] + 1); f[u] = max(f[u], f[v] + 1); } if (fa[v] != u && dfn[u] < dfn[v]) { //circle cnt = 0; while (v != fa[u]) cir[++cnt] = v, v = fa[v]; gao(); for (int j = 1; j < cnt; ++j) f[u] = max(f[u], f[cir[j]] + min(j, cnt - j)); } } } int main() { int n, m; memset(head, -1, sizeof(head)); read(n), read(m); for (int i = 1, x, y, z; i <= m; ++i) { read(x), read(y); for (int j = 1; j < x; ++j) { read(z); add(y, z); y = z; } } fa[1] = -1; dfs(1); printf("%d ", ans); return 0; }
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生