bzoj 1023 仙人掌图

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;
}
波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » bzoj 1023 仙人掌图

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡