http://www.lydsy.com/JudgeOnline/problem.php?id=1791
http://www.spoj.com/OI/problems/ISLAND/

D2T1 Islands

Brief description:

给定一个树加一条边。。求这个图的最长链。

Analysis:

Codeforces Beta Round #88

一棵树加一条边就是会有一个环。。讨论最长链。。

不在环上。。那么规约到树上最长链。。
在环上。。

那么设 d[i] 表示环上某个点向下所能到达的最远点。
。。 s[i] 表示环上第 0 个结点，沿着正方向到第 i 个结点之间的距离。。。
。。dist(i, j) 表示环上两个点的最长路径。。讨论方向。。
。。有 dist(i, j) = max(s[i] – s[j], ss – (s[i] – s[j))

。。ss 表示整个环的长度。。

答案就是 max{ d[i] + d[j] + dist(i, j) | j < i } 把上式拆开。。 就是每次。。找。。 max{ d[i] + s[i] + max(d[j] - s[j]), ss + d[i]-s[i] +max(d[j] + s[j]); } 然后 O(n) 扫描就可以了。。。 [cpp] //}/* .................................................................................................................................. */ const int N = int(1e6) + 9, M = 2*N; LL dd[N], d[N], s[N]; int c[N]; int nn; int Q[N], cz, op, uu; int hd[N], prd[M], suc[M], to[M], ww[N]; int n; #define aa to[i^1] #define bb to[i] #define w ww[i/2] inline void del(int i){ if (hd[aa] == i) prd[hd[aa] = suc[i]] = 0; else suc[prd[suc[i]] = prd[i]] = suc[i]; } inline void dell(int i){ del(i), del(i^1); } int vis[N]; bool st[N]; #define v (bb) bool dfs(int u, int p = -1){ // Find_Circle vis[u] = 1; REP_G(i, u) if (i != p){ if (vis[v]) st[v] = 1; if (vis[v] || dfs(v, i^1)){ c[nn] = v, s[nn+1] = s[nn] + w, ++nn, dell(i); return !st[u]; } } return 0; } LL f(int x){ nn = 0, dfs(x); LL z = 0; REP(ii, nn){ int s = c[ii], ss = s; dd[ii] = 0; cz = 0, op = 1; Q[0] = s; d[s] = 0; vis[s] = 2; while (cz < op){ int u = Q[cz++]; REP_G(i, u) if (vis[v] != 2){ d[v] = d[u] + w; vis[v] = 2, Q[op++] = v; if (d[v] > dd[ii]){ dd[ii] = d[v]; ss = v; } } } cz = 0, op = 1; Q[0] = ss, d[ss] = 0; vis[ss] = 3; while (cz < op){ int u = Q[cz++]; REP_G(i, u) if (vis[v] != 3){ d[v] = d[u] + w; vis[v] = 3, Q[op++] = v; checkMax(z, d[v]); } } } #define d dd LL ss=s[nn],pre1=d[0]-s[0],pre2=d[0]+s[0]; FOR(i,1,nn){ checkMax(z, d[i]+max(s[i]+pre1,ss-s[i]+pre2)); checkMax(pre1, d[i]-s[i]), checkMax(pre2, d[i]+s[i]); } return z; } int main(){ #ifndef ONLINE_JUDGE freopen("isl19g.in", "r", stdin); freopen("isl5.txt", "w", stdout); #endif RD(n); for (int i=2,a=1;i<=n<<1;++a){ aa = a, RD(bb, w); prd[hd[aa]] = i, suc[i] = hd[aa], hd[aa] = i++; prd[hd[aa]] = i, suc[i] = hd[aa], hd[aa] = i++; } LL z = 0; REP_1(i, n) if (!vis[i]) z += f(i); OT(z); } [/cpp]

Posted by xiaodao
Category: 日常