|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
专题包括  
点双, 边双, 强连通分量, 圆方树
需要注意的是这些割点割边强连通分量的判定方式不要搞混
SCC 序很重要, 有时候不需要建新图, 可以直接通过 SCC 编号来看, SCC 小的是在底下找到的, 大的是在上面找到的
遇到连通性相关要考虑这些算法进行简化, 别忘了线段树优化建图等等辅助
思想就是把图变成树, 做树上问题
有向图的 SCC (强连通分量)
模板void Tarjan(int u) {
low[u] = dfn[u] = ++tot;
stk[++top] = u;
instk[u] = 1;
for (auto v : e[u]) {
if (!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instk[v])
low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
int v;
scc++;
while (1) {
v = stk[top--];
instk[v] = 0;
id[v] = scc;
if (v == u)
break;
}
}
}
一般就是用来缩点然后把图变成 DAG 的, 可以跑 dp 或者别的
G - 拿钱走人
给个点条边的有向图，每个点有一些钱，当你经过这个点时可以拿走这些钱。
现在有一个起点和多个终点，你需要从起点出发，在某个终点结束，并且带走尽量多的钱，问你最多能带走多少钱？
缩点然后拓扑排序跑 dp#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
vector<int> e[N], g[N];
int n, m, p, s;
int dfn[N], low[N], tot;
int stk[N], top;
bitset<N> instk, ised;
int val[N], cnt, id[N];
int arr[N], f[N];
void Tarjan(int u) {
dfn[u] = low[u] = ++tot;
stk[++top] = u;
instk[u] = 1;
for (auto v : e[u]) {
if (!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instk[v])
low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
int v;
cnt++;
while (1) {
v = stk[top--];
instk[v] = 0;
id[v] = cnt;
val[cnt] += arr[v];
if (u == v)
break;
}
}
}
// g 图上的 DP
int dfs(int u) {
if (f[u] > 0)
return f[u];
f[u] = -1e9;
if (ised[u])
f[u] = 0;
for (auto v : g[u]) {
f[u] = max(f[u], dfs(v));
}
f[u] += val[u];
return f[u];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
e[a].emplace_back(b);
}
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
// 必须注意不能和上面的循环一起写, 调代码的时候注意看当前有没有没求过的数值
for (int i = 1; i <= n; i++) {
if (!dfn[i])
Tarjan(i);
}
cin >> s >> p;
s = id[s];
for (int i = 1; i <= p; i++) {
int x;
cin >> x;
ised[id[x]] = 1;
}
// 建图
for (int i = 1; i <= n; i++) {
for (auto j : e[i]) {
if (id[i] != id[j]) {
g[id[i]].emplace_back(id[j]);
}
}
}
cout << dfs(s);
return 0;
}
P3119 [USACO15JAN] Grass Cownoisseur G
这里本来应该拓扑排序的, 但是我们只关心能不能到, 所以按照 scc 编号的大小关心来看就好, 最后判断能否拼起来#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> e[N], g[N];
int n, m;
int dfn[N], low[N], tot;
int bel[N], scc, siz[N];
int stk[N], top;
bitset<N> instk;
void Tarjan(int u) {
dfn[u] = low[u] = ++tot;
stk[++top] = u;
instk[u] = 1;
for (auto v : e[u]) {
if (!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instk[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
int v;
scc++;
do {
v = stk[top--];
instk[v] = 0;
bel[v] = scc;
siz[scc]++;
} while (u != v);
}
}
// 正向, 反向
int a[N], b[N], ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
e[a].emplace_back(b);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i])
Tarjan(i);
}
if(scc == 1){
cout << siz[1];
return 0;
}
for (int i = 1; i <= n; i++) {
for (auto j : e[i]) {
if (bel[i] != bel[j]) {
g[bel[i]].emplace_back(bel[j]);
}
}
}
memset(a, -0x3f, sizeof(a));
memset(b, -0x3f, sizeof(b));
a[bel[1]] = siz[bel[1]];
b[bel[1]] = 0;
// bel[1] 能到达地方的最大值
for (int i = bel[1]; i; i--) {
for (auto j : g[i]) {
a[j] = max(a[j], a[i] + siz[j]);
}
}
// 能到达 bel[1] 的最大值
for (int i = bel[1] + 1; i <= scc; i++) {
for (auto j : g[i]) {
b[i] = max(b[i], b[j] + siz[i]);
}
}
for (int i = 1; i <= scc; i++) {
for (auto j : g[i]) {
// 想改变方向的是 i-j 这条边, i 自然是在 bel[1] 上面, j 在 bel[1] 下面
// 如果不是这样就不用改了, 自己成环了
if (i >= bel[1] && j <= bel[1]) {
ans = max(ans, a[j] + b[i]);
}
}
}
cout << ans;
return 0;
}
有向图的 vDCC(点双连通分量) eDCC(边双连通分量) 圆方树
BZOJ 3331
建圆方树, 树上差分vector<int> e[N], rst[M];
// 圆方树: 找出所有 vDCC, 每个点断边, 每个点向含有这个点的 vDCC 连边
int dfn[N], low[N], tot;
int stk[N], top, dcc;
void Tarjan(int u) {
dfn[u] = low[u] = ++tot;
stk[++top] = u;
for (auto v : e[u]) {
if (!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
int cur = 0;
dcc++;
while (1) {
cur = stk[top--];
rst[cur].emplace_back(dcc);
rst[dcc].emplace_back(cur);
if (cur == v)
break;
}
rst[u].emplace_back(dcc);
rst[dcc].emplace_back(u);
}
} else
low[u] = min(low[u], dfn[v]);
}
}
一九八四
给一个图, 有操作
1 a b x y 问删掉 (x, y) 这个边, a 和 b 能不能连通
2 a b x 问删掉 x 这个点, a 和 b 能不能连通
先求一下 low 和 dfn, 考虑在搜索树上分类讨论(这玩意一定要分清楚)// x 是否是 y 的子节点
bool Issub(int x, int y) { return (dfn[x] >= dfn[y] && dfn[x] <= r[y]); }
void Up(int& x, int dist) {
for (int i = 17; i >= 0; i--) {
if ((dist >> i) & 1) {
x = f[x][i];
}
}
}
bool Checkdege(int a, int b, int x, int y) {
// 让 x 是 y 的子节点
if (dfn[x] < dfn[y])
swap(x, y);
// 不是树边
if (f[x][0] != y)
return 1;
// 都在或者都不在子树
if (Issub(a, x) == Issub(b, x))
return 1;
// 如果有一个点在子树, 判断 (x, y) 是否是割边
return (low[x] < dfn[x]);
}
bool Checkcutv(int a, int b, int x) {
// 都不在子树
if (!Issub(a, x) && !Issub(b, x))
return 1;
// 都在子树, 看看 lca 是否是 x
if (Issub(a, x) && Issub(b, x)) {
Up(a, dep[a] - dep[x] - 1);
Up(b, dep[b] - dep[x] - 1);
return (a == b || (low[a] < dfn[x] && low[b] < dfn[x]));
}
// 其中一个在子树, 判断割点
if (Issub(b, x) && !Issub(a, x))
swap(a, b);
Up(a, dep[a] - dep[x] - 1);
return (low[a] < dfn[x]);
}
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2024-8-11 21:10:59
置顶卡
千斤顶
显身卡
楼主
发表于 2024-8-15 09:39:04
