サボテンきそ
8899 ワード
定義＃テイギ＃
つまり、各エッジは最大1つのリングに属します.
用途
人の出した毒瘤を解いて毒瘤を出してどうせ学ばなければならない...
練習問題
サボテンの最大独立集
Bzoj 4316:小Cの独立セット
やり方
リングがなければ木(DP)リングにぶつかったらリングの上の(DP)を1回作ればいいので、1つの点を挙げて選択すればいい
サボテンの直径
Bzoj 1023:[SHOI 2008]cactusサボテン図
やり方
やはりリングがないときは木(DP)リングがあるときはリングの合併を考えて毎回半分のリングしか考えないので、どちらに行くか考えずに単調な列を書いてポイントごとに2回入隊し、2回目はリング長を加えてキューヘッドを弾くたびに半分まで弾きます
サボテン最短
Bzoj 2125:最短
やり方
まず、丸い木ができてから、木の上で((u,v))の辺権が(u,v)に続く最短路の差が倍増するたびに(lca)、もし(lca)が円点であれば、辺権とそうでなければ方点であり、2つの点が(lca)にジャンプする前の最後の点が1つのリングにないかどうかを判断します.答えは辺権とそうでなければ、この2つの点が(lca)前の最後の点にジャンプする間の最短ルートを計算し、これを計算する値が答えです.
の最後の部分
ブロガー太菜はこれだけしかできません...
転載先:https://www.cnblogs.com/cjoieryl/p/9116001.html
つまり、各エッジは最大1つのリングに属します.
用途
人の出した毒瘤を解いて毒瘤を出してどうせ学ばなければならない...
練習問題
サボテンの最大独立集
Bzoj 4316:小Cの独立セット
やり方
リングがなければ木(DP)リングにぶつかったらリングの上の(DP)を1回作ればいいので、1つの点を挙げて選択すればいい
# include
# 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;
} サボテンの直径
Bzoj 1023:[SHOI 2008]cactusサボテン図
やり方
やはりリングがないときは木(DP)リングがあるときはリングの合併を考えて毎回半分のリングしか考えないので、どちらに行くか考えずに単調な列を書いてポイントごとに2回入隊し、2回目はリング長を加えてキューヘッドを弾くたびに半分まで弾きます
# include
# 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;
} サボテン最短
Bzoj 2125:最短
やり方
まず、丸い木ができてから、木の上で((u,v))の辺権が(u,v)に続く最短路の差が倍増するたびに(lca)、もし(lca)が円点であれば、辺権とそうでなければ方点であり、2つの点が(lca)にジャンプする前の最後の点が1つのリングにないかどうかを判断します.答えは辺権とそうでなければ、この2つの点が(lca)前の最後の点にジャンプする間の最短ルートを計算し、これを計算する値が答えです.
# include
# 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 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