仙人掌基础

定义

大概就是:连通图,每条边最多只属于一个环

用处

别人出的毒瘤
出毒瘤题
反正要学。。。

习题

仙人掌的最大独立集

Bzoj4316: 小C的独立集

做法

没有环就是树(DP)
碰到环就做一遍环上的(DP)就好了,枚举一下一个点是否选即可

# include <bits/stdc++.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;

IL int Input(){
    RG int x = 0, z = 1; RG char c = getchar();
    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x * z;
}

const int maxn(2e5 + 5);

int n, m, dfn[maxn], low[maxn], idx, fa[maxn], f[2][maxn], ans;

struct Edge{
    int first[maxn], cnt, nxt[maxn], to[maxn];

    IL void Init(){
        cnt = 0, Fill(first, -1);
    }

    IL void Add(RG int u, RG int v){
        nxt[cnt] = first[u], to[cnt] = v, first[u] = cnt++;
    }
} e1;

IL void Solve(RG int x, RG int u){
    RG int f0 = f[0][x], f1 = max(f[1][x], f[0][x]);
    for(RG int i = fa[x]; i != u; i = fa[i]){
        RG int tmp = f0;
        f0 = f1 + f[0][i], f1 = max(f0, tmp + max(f[0][i], f[1][i]));
    }
    f[0][u] += max(f1, f0), f0 = f1 = f[0][x];
    for(RG int i = fa[x]; i != u; i = fa[i]){
        RG int tmp = f0;
        f0 = f1 + f[0][i], f1 = max(f0, tmp + max(f[0][i], f[1][i]));
    }
    f[1][u] += f0;
}

IL void Tarjan(RG int u, RG int fe){
    dfn[u] = low[u] = ++idx, f[1][u] =1, f[0][u] = 0;
    for(RG int e = e1.first[u]; e != -1; e = e1.nxt[e]){
        RG int v = e1.to[e];
		if(e == fe) continue;
        if(!dfn[v]) fa[v] = u, Tarjan(v, e ^ 1), low[u] = min(low[u], low[v]);
        else low[u] = min(low[u], dfn[v]);
        if(low[v] > dfn[u]) f[1][u] += f[0][v], f[0][u] += max(f[0][v], f[1][v]);
    }
    for(RG int e = e1.first[u]; e != -1; e = e1.nxt[e])
        if(fa[e1.to[e]] != u && dfn[e1.to[e]] > dfn[u]) Solve(e1.to[e], u);
}

int main(){
    e1.Init(), n = Input(), m = Input();
    for(RG int i = 1; i <= m; ++i){
        RG int u = Input(), v = Input();
        e1.Add(u, v), e1.Add(v, u);
    }
    for(RG int i = 1; i <= n; ++i)
        if(!dfn[i]) Tarjan(i, -1), ans += max(f[0][i], f[1][i]);
    printf("%d
", ans);
    return 0;
}

仙人掌的直径

Bzoj1023: [SHOI2008]cactus仙人掌图

做法

还是没有环的时候树(DP)
有环的时候考虑环的合并
每次只考虑一半的环,这样就不用考虑走哪边
然后写一个单调队列
每个点入队两次,第二次时候给他加上环长
每次弹队列头,弹到只有一半为止

# include <bits/stdc++.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;

IL int Input(){
	RG int x = 0, z = 1; RG char c = getchar();
	for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
	for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x * z;
}

const int maxn(2e5 + 5);

int n, m, dfn[maxn], low[maxn], idx, fa[maxn], f[maxn], ans, deep[maxn], p[maxn], q[maxn];

struct Edge{
	int first[maxn], cnt, nxt[maxn], to[maxn];

	IL void Init(){
		cnt = 0, Fill(first, -1);
	}

	IL void Add(RG int u, RG int v){
		nxt[cnt] = first[u], to[cnt] = v, first[u] = cnt++;
	}
} e1;

IL void Solve(RG int x, RG int u){
	RG int len = 0, l = 0, r = -1;
	for(RG int i = x; i != u; i = fa[i]) p[++len] = i;
	p[++len] = u, reverse(p + 1, p + len + 1);
	for(RG int i = 1; i <= len; ++i) p[len + i] = p[i];
	RG int half = len >> 1; len += len;
	for(RG int i = 1; i <= len; ++i){
		while(l <= r && i - q[l] > half) ++l;
		if(l <= r) ans = max(ans, f[p[i]] + f[p[q[l]]] + i - q[l]);
		while(l <= r && f[p[i]] - i > f[p[q[r]]] - q[r]) --r;
		q[++r] = i;
	}
	for(RG int i = x; i != u; i = fa[i])
		f[u] = max(f[u], f[i] + min(deep[i] - deep[u], deep[x] - deep[i] + 1));
}

IL void Tarjan(RG int u, RG int fe){
	dfn[u] = low[u] = ++idx;
	for(RG int e = e1.first[u]; e != -1; e = e1.nxt[e]){
		RG int v = e1.to[e];
		if(e == fe) continue;
		if(!dfn[v]){
			fa[v] = u, deep[v] = deep[u] + 1;
			Tarjan(v, e ^ 1), low[u] = min(low[u], low[v]);
		}
		else low[u] = min(low[u], dfn[v]);
		if(low[v] > dfn[u]){
			ans = max(ans, f[u] + f[v] + 1);
			f[u] = max(f[u], f[v] + 1);
		}
	}
	for(RG int e = e1.first[u]; e != -1; e = e1.nxt[e])
		if(fa[e1.to[e]] != u && dfn[e1.to[e]] > dfn[u])
			Solve(e1.to[e], u);
}

int main(){
	e1.Init(), n = Input(), m = Input();
	for(RG int i = 1, a, b, l; i <= m; ++i)
		for(l = Input() - 1, a = Input(); l; --l)
			b = Input(), e1.Add(a, b), e1.Add(b, a), a = b;
	Tarjan(1, -1);
	printf("%d
", ans);
	return 0;
}

仙人掌最短路

Bzoj2125: 最短路

做法

首先你得会圆方树
然后树上((u, v))边权为跟到(u,v)的最短路之差
每次倍增跳到(lca),如果(lca)为圆点,那么就是边权和
否则为方点,判断两个点跳到(lca)前的最后一个点是否在一个环中
若不在,答案就是边权和
否则,计算这两个点跳到(lca)前的最后一个点之间的最短路,算上这个的值就是答案

# include <bits/stdc++.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;

IL int Input(){
	RG int x = 0, z = 1; RG char c = getchar();
	for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
	for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x * z;
}

const int maxn(4e4 + 5);
const ll inf(1e18);

int n, m, dfn[maxn], low[maxn], idx, fa[20][maxn];
int sta[maxn], top, tot, bel[maxn], vis[maxn], deep[maxn];
ll dis[maxn], len[maxn], d[maxn];
queue <int> q;

struct Edge{
	int first[maxn], cnt, nxt[maxn], to[maxn], w[maxn];

	IL void Init(){
		cnt = 0, Fill(first, -1);
	}

	IL void Add(RG int u, RG int v, RG int ww){
		nxt[cnt] = first[u], to[cnt] = v, w[cnt] = ww, first[u] = cnt++;
	}
} e1, e2;

IL void Tarjan(RG int u){
	dfn[u] = low[u] = ++idx, sta[++top] = u;
	for(RG int e = e1.first[u]; e != -1; e = e1.nxt[e]){
		RG int v = e1.to[e];
		if(!dfn[v]){
			d[v] = d[u] + e1.w[e];
			Tarjan(v), low[u] = min(low[u], low[v]);
			if(low[v] >= dfn[u]){
				RG int x = sta[top]; ++tot;
				for(RG int p = e1.first[x]; p != -1; p = e1.nxt[p])
					if(e1.to[p] == u) len[tot] = d[x] + e1.w[p] - d[u];
				do{
					x = sta[top--], bel[x] = tot;
					e2.Add(tot, x, dis[x] - dis[u]);
					e2.Add(x, tot, dis[x] - dis[u]);
				} while(x != v);
				e2.Add(tot, u, 0), e2.Add(u, tot, 0);
			}
		}
		else low[u] = min(low[u], dfn[v]);
	}
}

IL void SPFA(){
	for(RG int i = 1; i <= n; ++i) dis[i] = inf;
	dis[1] = 0, vis[1] = 1, q.push(1);
	while(!q.empty()){
		RG int u = q.front(); q.pop();
		for(RG int e = e1.first[u]; e != -1; e = e1.nxt[e]){
			RG int v = e1.to[e], w = e1.w[e];
			if(dis[u] + w < dis[v]){
				dis[v] = dis[u] + w;
				if(!vis[v]) vis[v] = 1, q.push(v);
			}
		}
		vis[u] = 0;
	}
}

IL void Dfs(RG int u, RG int ff){
	for(RG int e = e2.first[u]; e != -1; e = e2.nxt[e]){
		RG int v = e2.to[e];
		if(v != ff) fa[0][v] = u, deep[v] = deep[u] + 1, Dfs(v, u);
	}
}

IL ll Query(RG int u, RG int v){
	RG int x = u, y = v;
	if(deep[y] > deep[x]) swap(x, y);
	for(RG int j = 15; ~j; --j) if(deep[fa[j][x]] >= deep[y]) x = fa[j][x];
	if(x == y) return dis[u] + dis[v] - dis[x] * 2;
	for(RG int j = 15; ~j; --j) if(fa[j][x] != fa[j][y]) x = fa[j][x], y = fa[j][y];
	if(fa[0][x] <= n || bel[x] != bel[y]) return dis[u] + dis[v] - dis[fa[0][x]] * 2;
	RG ll ff = fa[1][x], mind = abs(d[x] - d[y]);
	mind = min(mind, len[bel[x]] - mind);
	return dis[u] + dis[v] - dis[x] - dis[y] + mind;
}

int main(){
	e1.Init(), e2.Init();
	tot = n = Input(), m = Input();
	RG int t = Input();
	for(RG int i = 1; i <= m; ++i){
		RG int u = Input(), v = Input(), w = Input();
		e1.Add(u, v, w), e1.Add(v, u, w);
	}
	SPFA(), Tarjan(1), Dfs(1, 0);
	for(RG int j = 1; j <= 15; ++j)
		for(RG int i = 1; i <= tot; ++i)
			fa[j][i] = fa[j - 1][fa[j - 1][i]];
	for(RG int i = 1; i <= t; ++i){
		RG int u = Input(), v = Input();
		printf("%lld
", Query(u, v));
	}
	return 0;
}

完结

博主太菜了只会这些。。。

原文地址:https://www.cnblogs.com/cjoieryl/p/9116001.html