## 【算法笔记】仙人掌

ps：感觉CA的东西比VFK的实用？
psx2：感觉wc上这张图还是很带感的，贴上来 =￣ω￣=

## 【POJ 3567】Cactus Reloaded

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
#include<stack>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 100000+9;
const int M = N*4;

int n,m,ring_cnt,num[N],nod_cnt,que[N*2],frt,bak=1;
vector<int> rings[M];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

inline void Add_Edge(int u, int v, int w){
static int T = 1;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void DFS(int w, int f){
num[w] = ++nod_cnt;
for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
if (!num[to[i]]) que[++frt]=i, DFS(to[i],w) ,frt--;
else if (num[to[i]] < num[w]) {
rings[++ring_cnt].push_back(i);
for (int j=frt;j;j--)
if (to[que[j]] == to[i]) break;
else rings[ring_cnt].push_back(que[j]);
}
}
}

inline void prework(){
for (int k=1;k<=ring_cnt;k++) {
int sz = rings[k].size(), top = to[rings[k][0]];
for (int i=0,tmp;i<sz;i++) {
tmp = to[rings[k][i]];
to[rings[k][i]] = to[rings[k][i]^1] = 0;
rings[k][i] = tmp;
for (int i=1;i<sz;i++) Add_Edge(cnt,rings[k][i],min(i,sz-i));
}
}

void Get_Ans(int w, int f){
for (int i=head[w];i;i=nxt[i]) if (to[i] && to[i] != f){
Get_Ans(to[i],w);
if (w <= n) vout = max(vout, g[w] + g[to[i]] + cost[i]);
g[w] = max(g[w], g[to[i]] + cost[i]);
}
}

inline void DP(){
static int buf[N*2];
for (int k=1;k<=ring_cnt;k++) {
int sz = rings[k].size(), top = rings[k][0];
int tmp = g[top]; g[top] = 0; frt = 0; bak = 1;
for (int i=0;i<sz;i++) buf[i+1] = buf[i+1+sz] = rings[k][i];
for (int i=1;i<=sz*2;i++) {
while (bak <= frt && i-que[bak] > sz/2) bak++;
if (bak <= frt) vout = max(vout, i+g[buf[i]] + g[buf[que[bak]]]-que[bak]);
while (bak <= frt && g[buf[que[frt]]]-que[frt] <= g[buf[i]]-i) frt--;
que[++frt] = i;
} g[top] = tmp;
}
}

int main(){
cnt = n = read(); m = read();
for (int len,i=1,tmp;i<=m;i++) {
} DFS(1,1); prework(); Get_Ans(1,1); DP();
printf("%d\n",vout);
return 0;
}


## 【BZOJ 1023】[SHOI2008] Cactus仙人掌图

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
#include<stack>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 100000+9;
const int M = N*4;

int n,m,ring_cnt,num[N],nod_cnt,que[N*2],frt,bak=1;
vector<int> rings[M];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

inline void Add_Edge(int u, int v, int w){
static int T = 1;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void DFS(int w, int f){
num[w] = ++nod_cnt;
for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
if (!num[to[i]]) que[++frt]=i, DFS(to[i],w) ,frt--;
else if (num[to[i]] < num[w]) {
rings[++ring_cnt].push_back(i);
for (int j=frt;j;j--)
if (to[que[j]] == to[i]) break;
else rings[ring_cnt].push_back(que[j]);
}
}
}

inline void prework(){
for (int k=1;k<=ring_cnt;k++) {
int sz = rings[k].size(), top = to[rings[k][0]];
for (int i=0,tmp;i<sz;i++) {
tmp = to[rings[k][i]];
to[rings[k][i]] = to[rings[k][i]^1] = 0;
rings[k][i] = tmp;
for (int i=1;i<sz;i++) Add_Edge(cnt,rings[k][i],min(i,sz-i));
}
}

void Get_Ans(int w, int f){
for (int i=head[w];i;i=nxt[i]) if (to[i] && to[i] != f){
Get_Ans(to[i],w);
if (w <= n) vout = max(vout, g[w] + g[to[i]] + cost[i]);
g[w] = max(g[w], g[to[i]] + cost[i]);
}
}

inline void DP(){
static int buf[N*2];
for (int k=1;k<=ring_cnt;k++) {
int sz = rings[k].size(), top = rings[k][0];
int tmp = g[top]; g[top] = 0; frt = 0; bak = 1;
for (int i=0;i<sz;i++) buf[i+1] = buf[i+1+sz] = rings[k][i];
for (int i=1;i<=sz*2;i++) {
while (bak <= frt && i-que[bak] > sz/2) bak++;
if (bak <= frt) vout = max(vout, i+g[buf[i]] + g[buf[que[bak]]]-que[bak]);
while (bak <= frt && g[buf[que[frt]]]-que[frt] <= g[buf[i]]-i) frt--;
que[++frt] = i;
} g[top] = tmp;
}
}

int main(){
cnt = n = read(); m = read();
for (int len,i=1,tmp;i<=m;i++) {
} DFS(1,1); prework(); Get_Ans(1,1); DP();
printf("%d\n",vout);
return 0;
}


## 【BZOJ 3047】Freda的传呼机

#include<iostream>
#include<cstdio>
#include<vector>
#define abs(x) ((x)<0?-(x):(x))
using namespace std;

const int MAXN = 40000;

int ori[MAXN],dep[MAXN],dis[MAXN],cost[MAXN],length[MAXN];
vector<int> rings[MAXN];

char c=getchar(); int buf=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
return buf*f;
}

inline void AddEdge(int u, int v, int c){
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = c;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = c;
}

void DFS(int w, int f){
static int T = 0, tot = 0;
num[w] = lowlink[w] = ++T; que[++tot] = w;
for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
if (!num[to[i]]) {
DFS(to[i],w);
if (lowlink[to[i]] > num[w]) tot--;
else {
ring_cnt++;
while (que[tot] != w) rings[ring_cnt].push_back(que[tot--]);
rings[ring_cnt].push_back(w);
}
}
}

inline void prework(){
for (int k=1;k<=ring_cnt;k++) {
int sz = rings[k].size();
int rt = rings[k][sz-1],tmp=0;
for (int i=1;i<=sz;i++) que[i] = rings[k][i-1];
que[0] = rt; que[sz+1] = que[1];

for (int w=1;w<=sz;w++) {
if (to[i] == que[w-1]) to[i] = 0, tmp += cost[i];
else if (to[i] == que[w+1]) to[i] = 0;
ori[que[w]] = tmp;
} ori[rt] = 0; length[k] = tmp;
for (int i=1;i<sz;i++) ring_num[que[i]] = k;
for (int i=1;i<sz;i++) AddEdge(rt,que[i],min(ori[que[i]],tmp-ori[que[i]]));
}
}

void GetDis(int w, int f){
fa[w][0] = f; dep[w] = dep[f] + 1;
for (int i=head[w];i;i=nxt[i]) if (!dep[to[i]] && to[i])
dis[to[i]] = dis[w] + cost[i], GetDis(to[i],w);
}

inline void LCA_init(){
for (int k=1;k<=18;k++) for (int i=1;i<=n;i++)
fa[i][k] = fa[fa[i][k-1]][k-1];
}

inline int LCA(int a, int b, int &l1, int &l2) {
if (dep[a] < dep[b]) swap(a,b);
for (int k=18;~k;k--) if (dep[fa[a][k]] >= dep[b])
a = fa[a][k];
l1 = l2 = a;
if (a == b) return a;
for (int k=18;~k;k--) if (fa[a][k] != fa[b][k])
a = fa[a][k], b = fa[b][k];
l1 = a; l2 = b; return fa[a][0];
}

int  main(){
for (int i=1,a,b,c;i<=m;i++) a = read(), b = read(), c = read(), AddEdge(a, b, c);
DFS(1,0); prework(); dep[1] = 1; GetDis(1,0); LCA_init();

for (int i=1,u,v,l1,l2;i<=q;i++){
int lca = LCA(u, v, l1, l2);
if (ring_num[l1] && ring_num[l1] == ring_num[l2]) {
int len = abs(ori[l1] - ori[l2]);
len = min(length[ring_num[l2]]-len,len);
printf("%d\n",dis[u]+dis[v]-dis[l1]-dis[l2]+len);
} else printf("%d\n",dis[u]+dis[v]-2*dis[lca]);
}
return 0;
}


## 【BZOJ 2125】最短路

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
using namespace std;

const int MAXN = 10000+9;

int ring_cnt,fa[MAXN][16],dep[MAXN],length[MAXN],ring_num[MAXN],ori[MAXN],que[MAXN],fro;
vector<int> rings[MAXN];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void AddEdge(int a, int b, int c){
static int T = 0;
to[++T] = b; nxt[T] = head[a]; head[a] = T; cost[T] = c;
to[++T] = a; nxt[T] = head[b]; head[b] = T; cost[T] = c;
}

void DFS(int w, int f){
static int T = 0; fa[w][0] = f;
lowlink[w] = num[w] = ++T; que[++fro] = w;
for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
if (!num[to[i]]) {
DFS(to[i], w);
if (lowlink[to[i]] > num[w]) fro--;
else {
ring_cnt++; int nw = que[fro--];
while (nw != w) {
rings[ring_cnt].push_back(nw);
nw = que[fro--];
}
rings[ring_cnt].push_back(w); que[++fro] = w;
}
}
}

inline void prework(){
for (int k=1;k<=ring_cnt;k++) {
int size = rings[k].size();
int rt = rings[k][size-1],tmp=0;

for (int i=1;i<=size;i++) que[i] = rings[k][i-1];
que[0] = rt; que[size+1] = que[1];
for (int i=1;i<size;i++) ring_num[que[i]] = k, fa[que[i]][0] = rt;

for (int i=1;i<=size;i++) {
for (int j=head[que[i]];j;j=nxt[j]) {
if (to[j] == que[i-1]) to[j] = 0, tmp += cost[j];
else if (to[j] == que[i+1]) to[j] = 0;
}
ori[que[i]] = tmp;
} ori[rt] = 0; length[k] = tmp;
for (int i=1;i<size;i++) AddEdge(rt,que[i],min(ori[que[i]], tmp-ori[que[i]]));
}
}

void GetDis(int w){
for (int i=head[w];i;i=nxt[i]) if (!dis[to[i]] && to[i])
dis[to[i]]=dis[w]+cost[i], dep[to[i]] = dep[w] + 1, GetDis(to[i]);
}

inline void LCA_init() {
for (int k=1;k<=15;k++) for (int i=1;i<=n;i++)
fa[i][k] = fa[fa[i][k-1]][k-1];
}

inline int LCA(int a, int b, int &l1, int &l2){
if (dep[a] < dep[b]) swap(a,b);
for (int k=15;~k;k--) if (dep[fa[a][k]] >= dep[b]) a = fa[a][k];
l1 = l2 = a;
if (a == b) return a;
else {
for (int k=15;~k;k--) if (fa[a][k] != fa[b][k]) a = fa[a][k], b = fa[b][k];
l1 = a, l2 = b; return fa[a][0];
}
}

int main(){
for (int i=1,a,b,c;i<=m;i++)
DFS(1,0); prework();
dis[1] = dep[1] = 1; GetDis(1); LCA_init();
for (int i=1,a,b,r,lca1,lca2;i<=Q;i++){
r = LCA(a, b, lca1, lca2);
if (ring_num[lca1] && ring_num[lca1] == ring_num[lca2]) {
int len = abs(ori[lca1]-ori[lca2]);
len = min(len, length[ring_num[lca1]]-len);
printf("%d\n",dis[a]-dis[lca1]+dis[b]-dis[lca2]+len);
} else printf("%d\n",dis[a]+dis[b]-2*dis[r]);
}
return 0;
}


## 【模板库】仙人掌生成

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<vector>
using namespace std;

const int N = 10000;
const int Q = 10000;
const int INF = 10000;
const int block = 200;
const int MAXN = 100000;

int ord[MAXN],tmp,cnt,TMP;
vector<pair<int,int> > que;

inline int R(int lim) {
if (!lim) return 0;
else return rand()%lim+1;
}

int main(){
srand(time(0));
int n = N, q=R(Q);
for (int i=1;i<=n;i++) ord[i] = i;
for (int i=1;i<=n;i++) swap(ord[R(n)],ord[R(n)]);
for (int i=1;i<=n;) {
int len = min(R(n/block)+2,n-i+1);
for (int j=0;j<len-1;j++) que.push_back(make_pair(ord[i+j],ord[i+j+1]));
if (len > 2) que.push_back(make_pair(ord[i],ord[i+len-1]));
if (tmp) que.push_back(make_pair(ord[i+R(len)-1],tmp));
tmp = ord[i+R(len)-1]; i += len;
} cnt = que.size();
printf("%d %d %d\n",n,cnt,q);
for (int i=0;i<cnt;i++) {
int a = que[i].first;
int b = que[i].second;
int c = R(INF);
printf("%d %d %d\n",a,b,c);
}
for (int i=1;i<=q;i++)
cout<<R(n)<<' '<<R(n)<<endl;
return 0;
}