Contents
强连通分量
题目:P3387 缩点
题目大意:
给定一个 n 个点 m 条边有向图,每个点有一个权值,求一条路径,使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点,但是,重复经过的点,权值只计算一次。
分析:
先使用 tarjan 缩点,然后对图进行重构,再对拓扑图记忆化搜索。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 50;
const int M = 1e5 + 50;
int a[M], b[M], x[N];
int n, m;
int ans;
int head[N], tot;
struct Edge {
int nex, to;
}e[M];
void add(int a, int b) {
e[++tot] = {head[a], b};
head[a] = tot;
}
int dfn[N], low[N], in[N], sum;
int bel[N], col;
int g[N], f[N];
stack<int> s;
void tarjan(int u) {
dfn[u] = low[u] = ++sum;
s.push(u); in[u] = 1;
for (int i = head[u]; i; i = e[i].nex) {
int to = e[i].to;
if (!dfn[to]) {
tarjan(to);
low[u] = min(low[u], low[to]);
}
else if (in[to]) {
low[u] = min(low[u], dfn[to]);
}
}
if (low[u] == dfn[u]) {
col++;
do {
bel[u] = col;
u = s.top(); s.pop();
in[u] = 0;
}
while (low[u] != dfn[u]);
}
}
void search(int u) {
if (f[u]) return;
f[u] = g[u];
int maxson = 0;
for (int i = head[u]; i; i = e[i].nex) {
int to = e[i].to;
search(to);
maxson = max(maxson, f[to]);
}
f[u] += maxson;
}
void rebuild() {
memset(head, 0, sizeof(head));
tot = 0;
for (int i = 1; i <= m; i++) {
if (bel[a[i]] != bel[b[i]]) {
add(bel[a[i]], bel[b[i]]);
}
}
for (int i = 1; i <= n; i++) {
g[bel[i]] += x[i];
}
for (int i = 1; i <= col; i++) {
if (!f[i]) search(i);
ans = max(ans, f[i]);
}
}
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> x[i];
}
for (int i = 1; i <= m; i++) {
cin >> a[i] >> b[i];
add(a[i], b[i]);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i);
}
rebuild();
cout << ans << "\n";
return 0;
}
双连通分量
P2860 [USACO06JAN]Redundant Paths G
题目大意:
给你一个 n 个点 m 条边的无向图,问至少要加几条边,才可以使得任意两点间有至少两条不同的路径。
分析:
用 tarjan 求出双连通分量,得到了一颗树。树的叶子结点数 / 2 向上取整即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 50;
const int M = 2e4 + 50;
int n, m;
int a[M], b[M];
int ans;
int head[N], tot = 1; // 和网络流一样,初始化为1
struct Edge {
int nex, to;
}e[M];
void add(int a, int b) {
e[++tot] = {head[a], b};
head[a] = tot;
}
int dfn[N], low[N], in[N], sum;
int bel[N], col;
int vis[M];
int degree[N];
stack<int> s;
void tarjan(int u) {
dfn[u] = low[u] = ++sum;
s.push(u);
in[u] = 1;
for (int i = head[u]; i; i = e[i].nex) {
if (vis[i]) continue;
int to = e[i].to;
vis[i] = vis[i ^ 1] = 1; // 记录正反边
if (!dfn[to]) {
tarjan(to);
low[u] = min(low[u], low[to]);
}
else if (in[to]) {
low[u] = min(low[u], dfn[to]);
}
}
if (low[u] == dfn[u]) {
col++;
do {
bel[u] = col;
u = s.top(); s.pop();
in[u] = 0;
}
while (low[u] != dfn[u]);
}
}
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> a[i] >> b[i];
add(a[i], b[i]);
add(b[i], a[i]);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i);
}
for (int i = 1; i <= m; i++) {
if (bel[a[i]] != bel[b[i]]) {
degree[bel[a[i]]]++;
degree[bel[b[i]]]++;
}
}
for (int i = 1; i <= col; i++) {
if (degree[i] == 1) {
ans++;
}
}
cout << (ans + 1) / 2 << "\n";
return 0;
}
割点
题目大意:
给出一个 n 个点,m 条边的无向图,求图的割点。在无向连通图中,如果将其中一个点以及所有连接该点的边去掉,图就不再连通,那么这个点就叫做割点。
分析:
对于根节点,计算其子树数量,如果有 2 棵即以上的子树,就是割点。因为如果去掉这个点,这两棵子树就不能互相到达。
对于非根节点,有边 (u, v),如果 low[v]\ge dfn[u],此时 u 就是割点。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 50;
const int M = 2e5 + 50;
int n, m;
int ans;
int head[N], tot;
struct Edge
{
int nex, to;
}e[M];
void add(int a, int b) {
e[++tot] = {head[a], b};
head[a] = tot;
}
int dfn[N], low[N], sum;
int iscut[N];
void tarjan(int u, int rt) {
int cnum = 0;
dfn[u] = low[u] = ++sum;
for (int i = head[u]; i; i = e[i].nex) {
int to = e[i].to;
if (!dfn[to]) {
tarjan(to, rt);
low[u] = min(low[u], low[to]);
if (low[to] >= dfn[u] && u != rt) {
iscut[u] = 1;
}
if (u == rt) {
cnum++;
}
}
else {
low[u] = min(low[u], dfn[to]);
}
}
if (u == rt && cnum >= 2) {
iscut[u] = 1;
}
}
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1, a, b; i <= m; i++) {
cin >> a >> b;
add(a, b); add(b, a);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i, i);
}
for (int i = 1; i <= n; i++) {
if (iscut[i]) ans++;
}
cout << ans << "\n";
for (int i = 1; i <= n; i++) {
if (iscut[i]) {
cout << i << " ";
}
}
cout << "\n";
return 0;
}
2-SAT
题目大意:
有 n 个布尔变量 x_1\sim x_n,另有 m 个需要满足的条件,每个条件的形式都是 「x_i为 true
/ false
或 x_j 为 true
/ false
」。比如 x_1 为真或 x_3 为假、x_7 为假或 x_2为假。
2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。
第一行两个整数 n 和 m,意义如题面所述。接下来 m 行每行 4 个整数 i, a, j, b,表示 x_i 为 a 或 x_j 为 b (a, b\in {0,1})
如无解,输出 IMPOSSIBLE
;否则输出 POSSIBLE
。下一行 n 个整数 x_1\sim x_n(x_i\in{0,1}),表示构造出的解。
// a, b 都真,-a -> b, -b -> a
// a 假 b 真,a -> b, -b -> -a
// a 真 b 假,-a -> -b, b -> a
// a, b 都假,a -> -b, b -> -a
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e6 + 50;
vector<int> g[N];
int n, m;
int dfn[N], low[N], in[N], sum;
int bel[N], col;
stack<int> s;
void tarjan(int u) {
dfn[u] = low[u] = ++sum;
s.push(u); in[u] = 1;
for (int v : g[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (in[v]){
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
col++;
do {
bel[u] = col;
u = s.top(); s.pop();
in[u] = 0;
}
while (low[u] != dfn[u]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, xa, b, xb;
cin >> a >> xa >> b >> xb;
// x 点标号为 x,-x 标号为 x+n
g[a + n * (xa & 1)].pb(b + n * (xb ^ 1));
g[b + n * (xb & 1)].pb(a + n * (xa ^ 1));
}
for (int i = 1; i <= (n << 1); i++) {
if (!dfn[i]) tarjan(i);
}
for (int i = 1; i <= n; i++) {
if (bel[i] == bel[i + n]) {
cout << "IMPOSSIBLE\n";
return 0;
}
}
cout << "POSSIBLE\n";
for (int i = 1; i <= n; i++) {
cout << (bel[i] < bel[i + n]) << " ";
}
cout << "\n";
return 0;
}
例题:Gym 101987(2018 ICPC Seoul)K. TV Show Game
题目大意:
有一个字符串长度为 k,每个位置只包含字符 R 或者 B,现在有 n 个人,每个人都有 3 个猜想,问能否构造出一种字符串,使得满足每个人正确的猜想数都大于等于 2.
分析:
假设猜测的三个位置分别是 p1,p2,p3,那么就可以推出六条关系。
- $p1$ 错误 -> $p2$ 正确,
- $p1$ 错误 -> $p3$ 正确,
- $p2$ 错误 -> $p1$ 正确,
- $p2$ 错误 -> $p3$ 正确,
- $p3$ 错误 -> $p1$ 正确,
- $p3$ 错误 -> $p2$ 正确,
// R:x+n B:x
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int a, b, c, A, B, C; char x, y, z;
scanf("%d %c%d %c%d %c", &a, &x, &b, &y, &c, &z);
A = (x == 'R'), B = (y == 'R'), C = (z == 'R');
/*
g[a + n * A] 表示 p1 正确,则 g[a + n * (A ^ 1)] 表示 p1 错误
*/
g[a + n * (A ^ 1)].push_back(b + n * B);
g[a + n * (A ^ 1)].push_back(c + n * C);
g[b + n * (B ^ 1)].push_back(a + n * A);
g[b + n * (B ^ 1)].push_back(c + n * C);
g[c + n * (C ^ 1)].push_back(a + n * A);
g[c + n * (C ^ 1)].push_back(b + n * B);
}
for (int i = 1; i <= (n << 1); i++) {
if (!dfn[i]) tarjan(i);
}
for (int i = 1; i <= n; i++) {
if (bel[i] == bel[i + n]) {
printf("-1\n"); return 0;
}
}
for (int i = 1; i <= n; i++) {
printf(bel[i] < bel[i + n] ? "B" : "R");
}
puts("");
return 0;
}