滾回第一頁去了。。。

好吧，看了題解蒟蒻也寫不粗來，怎么辦捏？

看這個吧：Orz YDC巨巨；但是巨巨寫的程序又不優(yōu)美，于是程序Orz hzwer

其實這題的重點在于tarjan和單調(diào)隊列dp里"f的更新"和"ans的更新"的先后順序。。。

蒟蒻我研究半天才略懂還寫不出題解，真是弱到不行了我去 ≥v≤?~~~

?

1 /************************************************************** 2 Problem: 1023 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:176 ms 7 Memory:161276 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 13 using namespace std; 14 const int N = 50005; 15 const int M = 20000005; 16 17 struct edges{ 18 int next, to; 19 }e[M]; 20 int first[N], dep[N], f[N]; 21 int dfn[N], low[N], fa[N]; 22 int a[N * 2], q[N * 2], l, r; 23 int n, m, tot, cnt, ans; 24 25 inline int read(){ 26 int x = 0; 27 char ch = getchar(); 28 while (ch < '0' || ch > '9') 29 ch = getchar(); 30 31 while (ch >= '0' && ch <= '9'){ 32 x = x * 10 + ch - '0'; 33 ch = getchar(); 34 } 35 return x; 36 } 37 38 inline void add_edge(int X, int Y){ 39 e[++tot].next = first[X]; 40 first[X] = tot; 41 e[tot].to = Y; 42 } 43 44 void add_Edges(int x, int y){ 45 add_edge(x, y); 46 add_edge(y, x); 47 } 48 49 void DP(int root, int p){ 50 int T = dep[p] - dep[root] + 1; 51 for (int i = p; i != root; i = fa[i]) 52 a[T--] = f[i]; 53 a[T] = f[root]; 54 T = dep[p] - dep[root] + 1; 55 for (int i = 1; i <= T; ++i) 56 a[i + T] = a[i]; 57 q[1] = l = r = 1; 58 for (int i = 2; i <= 2 * T; ++i){ 59 while (l <= r && i - q[l] > T / 2) ++l; 60 ans = max(ans, a[i] + a[q[l]] + i - q[l]); 61 while (l <= r && a[q[r]] - q[r] <= a[i] - i) --r; 62 q[++r] = i; 63 } 64 for (int i = 2; i <= T; ++i) 65 f[root] = max(f[root], a[i] + min(i - 1, T - i + 1)); 66 } 67 68 void dfs(int p){ 69 low[p] = dfn[p] = ++cnt; 70 int x, y; 71 for (x = first[p]; x; x = e[x].next) 72 if ((y = e[x].to) != fa[p]){ 73 if (!dfn[y]){ 74 fa[y] = p, dep[y] = dep[p] + 1; 75 dfs(y); 76 low[p] = min(low[p], low[y]); 77 }else low[p] = min(low[p], dfn[y]); 78 if (dfn[p] < low[y]){ 79 ans = max(ans, f[p] + f[y] + 1); 80 f[p] = max(f[p], f[y] + 1); 81 } 82 } 83 for (x = first[p]; x; x = e[x].next) 84 if (fa[(y = e[x].to)] != p && dfn[p] < dfn[y]) 85 DP(p, y); 86 } 87 88 int main(){ 89 n = read(), m = read(); 90 int k, X, Y, i, j; 91 for (i = 1; i <= m; ++i){ 92 k = read(), X = read(); 93 for (j = 2; j <= k; ++j){ 94 Y = read(); 95 add_Edges(X, Y); 96 X = Y; 97 } 98 } 99 dfs(1); 100 printf("%d\n", ans); 101 return 0; 102 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/rausen/p/4044269.html

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的BZOJ1023 [SHOI2008]cactus仙人掌图的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。