【算法笔记】仙人掌

仙人掌这个东西,肯定是前排膜拜VFK:http://vfleaking.blog.uoj.ac/slide/89#/
然后嘛,就是狂膜一波CA爷:http://blog.csdn.net/creationaugust/article/details/48007069
仍然膜拜CA爷:http://blog.csdn.net/creationaugust/article/details/48022291

反正我的仙人掌栽培技术就这水平了
什么世界领先的动态仙人掌栽培技术,还是算了吧QAQ
ps:感觉CA的东西比VFK的实用?
psx2:感觉wc上这张图还是很带感的,贴上来 = ̄ω ̄=
21467125346712

【POJ 3567】Cactus Reloaded

题目传送门:http://poj.org/problem?id=3567

BZOJ_1023

#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 head[N],to[M],nxt[M],cost[M],g[N],vout,cnt;
int n,m,ring_cnt,num[N],nod_cnt,que[N*2],frt,bak=1;
vector<int> rings[M];

inline int read(){
	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;
		} Add_Edge(top,++cnt,0);
		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++) {
		len = read(); tmp = read();
		for (int j=1,t;j<len;j++) Add_Edge((t=read()),tmp,1), tmp=t;
	} DFS(1,1); prework(); Get_Ans(1,1); DP(); 
	printf("%d\n",vout);
	return 0;
}

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

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1023
数据生成器:http://paste.ubuntu.com/23106255/
测试数据:http://pan.baidu.com/s/1pLxVyQ3

仙人掌DP,调了好久QAQ
题解的话,让我们召唤CA爷:http://blog.csdn.net/creationaugust/article/details/48028117

值得一提的是,之前我尝试将其缩成一棵树之后,BFS两遍找直径
但wa了很久,很久。后来发现,因为走到环那里时,路径的长度是变化的,且入口不同->长度不同
所以两次BFS是错的,且无法通过多次BFS来保证正确性
换句话说,仙人掌的直径貌似只能这么DP?

另外值得一提的是,仙人掌的预处理的时候,确实只能存边,存点能找到反例(之前拍到过一组,但忘了记录下来)
换一句话来说,popoqqq的仙人掌是可以被卡掉的(好像是几个环连在一个点上)

另外的话,我仙人掌的板之前一直是错的,因为出题人数据太弱+自己数据太弱没有发现,这一份才是对的(能过neerc的数据我还是很自信的)
最后的话,仙人掌的题目,不套模板会快很多,套模板虽然代码风格统一,但写起来确实麻烦一些

#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 head[N],to[M],nxt[M],cost[M],g[N],vout,cnt;
int n,m,ring_cnt,num[N],nod_cnt,que[N*2],frt,bak=1;
vector<int> rings[M];

inline int read(){
	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;
		} Add_Edge(top,++cnt,0);
		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++) {
		len = read(); tmp = read();
		for (int j=1,t;j<len;j++) Add_Edge((t=read()),tmp,1), tmp=t;
	} DFS(1,1); prework(); Get_Ans(1,1); DP(); 
	printf("%d\n",vout);
	return 0;
}

【BZOJ 3047】Freda的传呼机

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3047

这题应该是基环树?然而不会基环树的做法QAQ
所以我们把他当成仙人掌来做吧! (*^_^*)

#include<iostream>
#include<cstdio>
#include<vector>
#define abs(x) ((x)<0?-(x):(x))
using namespace std;
 
const int MAXN = 40000;
 
int n,m,q,nxt[MAXN],to[MAXN],head[MAXN],que[MAXN];
int fa[MAXN][20],num[MAXN],lowlink[MAXN],ring_cnt,ring_num[MAXN];
int ori[MAXN],dep[MAXN],dis[MAXN],cost[MAXN],length[MAXN];
vector<int> rings[MAXN];
 
inline int read(){
    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 if (lowlink[to[i]] < num[w]) lowlink[w] = lowlink[to[i]];
            else {
                ring_cnt++; 
                while (que[tot] != w) rings[ring_cnt].push_back(que[tot--]);
                rings[ring_cnt].push_back(w); 
            }
        } else lowlink[w] = min(lowlink[w],num[to[i]]);
    }
}
 
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++) {
            for (int i=head[que[w]];i;i=nxt[i])
                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(){
    n = read(); m = read(); q = read();
    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++){
        u = read(), v = read();
        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_1023

【BZOJ 2125】最短路

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2125

仙人掌上求最短路
先搞成树,然后树怎么搞,这题就怎么搞

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
using namespace std;
 
const int MAXN = 10000+9;
 
int n,m,Q,lowlink[MAXN],num[MAXN],dis[MAXN],nxt[MAXN*4],to[MAXN*4],head[MAXN],cost[MAXN*4];
int ring_cnt,fa[MAXN][16],dep[MAXN],length[MAXN],ring_num[MAXN],ori[MAXN],que[MAXN],fro;
vector<int> rings[MAXN];
 
inline int read(){
    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 if (lowlink[to[i]] < num[w]) lowlink[w] = lowlink[to[i]];
            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;
            }
        } else lowlink[w] = min(lowlink[w], num[to[i]]);
    }
}
 
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(){
    n = read(); m = read(); Q = read();
    for (int i=1,a,b,c;i<=m;i++) 
        a = read(), b = read(), c = read(),
        AddEdge(a, b, c);
    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++){
        a = read(); b = read();
        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;
}

另外,这份代码在预处理环那里有问题
会被一个点连了几个环的情况卡成翔
正确的写法,参见BZOJ_1023

【模板库】仙人掌生成

生成仙人掌,输出最短路的询问

#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;
}