有感而发，今晚一定先写篇题解。这可是我AC的第一道紫题！
题目中说半连通子图指的是对于图$G(V, E)$，$\forall u, v \in V$ 有 $u \to v$ 或者 $v \to u$。当时我对于“或”的理解是异或，也就是二者不能同时存在。
——那这题基本没法做啊？比如我们作一次DFS，搜索的时候光是找到一条横叉边，就已经让人头疼怎么处理；更别说还要判环，还要找“最大”的半连通子图。
但有一点是可以确定的——当图中可以将环处理掉时，“半连通子图”将会是一条链。易知对于链上的节点$u, v$ (u是v的祖先)，都有$u \to v$。
中午憋不住了，问了已经AC的lty大佬。他告诉我这是可兼或。果然！于是我们自然想到，对于每一个SCC（强连通分量），必然满足“半连通子图”的定义。
所以我们立刻使用Tarjan执行缩点。完成后将得到一张DAG（有向无环图），这时就可以通过拓扑排序，累加以其结尾的链的个数了。我自然写出一份爆零代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 102400, M = 1048576;
int n, m, mod, u, v, head[N], headc[N];
struct edge {
int v, nxt;
} e[M];
struct c_edge {
int v, w, nxt;
} gc[M];
int st[N], dfn[N], low[N], top, num, c_cnt, c_e_cnt;
int c[N], c_node_cnt[N], prev_vis;
int sol_cnt[N], ind[N];
long long g_node_cnt[N], sol, max_g_cnt;
bool ins[N], ex_vis[N], has_outd[N], vis[N];
queue <int> q;
void tarjan (int x) {
low[x] = dfn[x] = ++num;
st[++top] = x, ins[x] = true;
for (int i = head[x]; i; i = e[i].nxt) {
if (!dfn[e[i].v]) {
tarjan (e[i].v);
low[x] = min (low[x], low[e[i].v]);
} else if (ins[e[i].v])
low[x] = min (low[x], dfn[e[i].v]);
}
if (low[x] == dfn[x]) {
++c_cnt; int y;
do {
y = st[top--], ins[y] = false;
c[y] = c_cnt, ++c_node_cnt[c_cnt];
} while (x != y);
}
}
void add_c (int x, int y, int w) {
gc[++c_e_cnt].v = y, gc[c_e_cnt].nxt = headc[x], gc[c_e_cnt].w = w, headc[x] = c_e_cnt;
}
void topo () {
q.push(0);
while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = headc[x]; i; i = gc[i].nxt) {
sol_cnt[gc[i].v] = (sol_cnt[gc[i].v] + sol_cnt[x]) % mod;
if (--ind[gc[i].v] == 0)
q.push(gc[i].v);
}
}
}
void bfs () {
q.push(0);
while (!q.empty()) {
int x = q.front(); q.pop();
vis[x] = false;
for (int i = headc[x]; i; i = gc[i].nxt) {
g_node_cnt[gc[i].v] = max(g_node_cnt[gc[i].v], g_node_cnt[x] + gc[i].w);
if (!vis[gc[i].v])
q.push(gc[i].v);
}
}
}
int main () {
/* 洛谷题库 P2272 [ZJOI2007]最大半连通子图 吴秋实 */
scanf ("%d%d%d", &n, &m, &mod);
for (int i = 1; i <= m; ++i) {
scanf ("%d%d", &u, &v);
e[i].nxt = head[u], e[i].v = v, head[u] = i;
}
// 缩点
for (int i = 1; i <= n; ++i)
if (!dfn[i]) tarjan (i);
for (int i = 1; i <= n; ++i)
for (int j = head[i]; j; j = e[j].nxt) {
if (c[e[i].v] == c[i]) continue;
add_c (c[i], c[e[i].v], c_node_cnt[c[e[i].v]]);
++ind[c[e[i].v]], has_outd[c[i]] = true;
}
for (int i = 1; i <= c_cnt; ++i)
if (ind[i] == 0) {
add_c (0, i, c_node_cnt[i]);
ind[i] = 1;
}
// 去除重边
for (int i = 1; i <= c_cnt; ++i) {
memset (ex_vis, 0, sizeof ex_vis);
prev_vis = 0;
for (int j = headc[i]; j; j = gc[j].nxt) {
if (ex_vis[gc[j].v])
gc[prev_vis].nxt = gc[j].nxt,
--ind[gc[j].v];
else ex_vis[gc[j].v] = true;
prev_vis = j;
}
}
// 作拓扑排序
sol_cnt[0] = 1;
topo ();
// BFS寻找最大解
bfs ();
for (int i = 1; i <= c_cnt; ++i) {
if (!has_outd[i])
sol = (sol + sol_cnt[i]) % mod;
max_g_cnt = max(max_g_cnt, g_node_cnt[i]);
}
printf("%lld\n%lld", max_g_cnt, sol);
return 0;
}又是TLE又是MLE又是WA的。
仔细一看，存在很大问题：
- 先进行一次拓扑排序找“方案数”，又用BFS找最大解。而且为了不漏解，BFS遍历了每一条可能的路径（甚至不是按照节点层数扩展的）（粗算时间复杂度是$O(\prod d^+(v))$，即每个点的出度的乘积），显然直接爆时间；
- 建缩点过后新图的代码写错了（细节啊！）。
将这些细枝末节的地方改正之后，再交，仍然爆零。并且查看输出信息发现，第一行（输出最大链长度）没有问题，但第二行（输出方案数）全部不正确。
冥思苦想了好久……修改了一些细节提交，仍然不正确。无奈，只得去题解板块寻找与我的相同的思路。但令人惊奇的是，这些题解求答案时，无一例外都有这个转移方程：
设以编号为$i$的SCC为结尾的最长链的条数为$g[i]$，长度为$f[i]$，有编号为$j$的SCC，$j \to i$，则有
$\begin{cases}
g[i] = g[i] + g[j] & (f[i] = f[j] + c\_cnt[i]); \\
g[i] = g[j], f[i] = f[j] + c\_cnt[i] & (f[i] < f[j] + c\_cnt[i]). \end{cases}$
为什么待扩展方案链长大于现有方案链长时才发生转移呢？我们再来读题——“若 $G’$ 是 $G$ 所有半连通子图中包含节点数最多的，则称$G’$是$G$的最大半连通子图。”
看来连题都读错了。它求的是“最长链数量”，而我求的是“以第$i$个SCC结尾的链的总方案数”。这样一来，转移方程也就可以理解了。现有方案更优，则直接按照现有方案信息转移；若同样优秀，则方案数累加。
我们再倒回去说说使用拓扑排序求解、转移答案的正确性。因为在拓扑排序中会记录每个点的入度，每遍历一条边$e<u, v>$都会将$v$入度减$1$，当且仅当$d^-(v) = 0$时才会将$v$入队，扩展节点。则易知这样可以保证每一个节点从入边获得最优解。
（哦对了，拓扑之前要去重边。）
时间复杂度$\mathbf{O}(|V| + |E|)$。AC代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 409600, M = 4096000;
int n, m, mod, u, v, head[N], headc[N];
struct edge {
int v, nxt;
} e[M];
struct c_edge {
int v, w, nxt;
} gc[M];
int st[N], dfn[N], low[N], top, num, c_cnt, c_e_cnt;
int c[N], c_node_cnt[N], prev_vis;
int sol_cnt[N], ind[N];
long long g_node_cnt[N], sol, max_g_cnt;
bool ins[N], ex_vis[N], has_outd[N], vis[N];
queue q;
void tarjan (int x) {
low[x] = dfn[x] = ++num;
st[++top] = x, ins[x] = true;
for (int i = head[x]; i; i = e[i].nxt) {
if (!dfn[e[i].v]) {
tarjan (e[i].v);
low[x] = min (low[x], low[e[i].v]);
} else if (ins[e[i].v])
low[x] = min (low[x], dfn[e[i].v]);
}
if (low[x] == dfn[x]) {
++c_cnt; int y;
do {
y = st[top--], ins[y] = false;
c[y] = c_cnt, ++c_node_cnt[c_cnt];
} while (x != y);
}
}
void add_c (int x, int y, int w) {
gc[++c_e_cnt].v = y, gc[c_e_cnt].nxt = headc[x], gc[c_e_cnt].w = w, headc[x] = c_e_cnt;
}
void topo () {
q.push(0);
while (!q.empty()) {
int x = q.front(); q.pop();
memset (ex_vis, 0, sizeof ex_vis);
for (int i = headc[x]; i; i = gc[i].nxt) {
if (!ex_vis[gc[i].v]) {
/* 题目中“最大半联通子图”的意思并不是单纯的“不同的”链的“方案数”叠加。 */
/* 细读它的定义，应该是有两条可能的链延展到同一个节点时，取节点数“最大”的一个，才是最大半连通子图。 */
/* 那么，链长相等时，就应该累加方案数。这才是正确的转移方式。 */
if (g_node_cnt[x] + gc[i].w > g_node_cnt[gc[i].v]) // 更好的方案！采取它进行转移。
sol_cnt[gc[i].v] = sol_cnt[x],
g_node_cnt[gc[i].v] = g_node_cnt[x] + gc[i].w;
else if (g_node_cnt[x] + gc[i].w == g_node_cnt[gc[i].v]) // 二者相等，将它们的前序方案累加。
sol_cnt[gc[i].v] = (sol_cnt[gc[i].v] % mod + sol_cnt[x] % mod) % mod;
ex_vis[gc[i].v] = true;
}
if (--ind[gc[i].v] == 0)
q.push(gc[i].v);
}
}
}
int main () {
/* 洛谷题库 P2272 [ZJOI2007]最大半连通子图 吴秋实 */
scanf ("%d%d%d", &n, &m, &mod);
for (int i = 1; i <= m; ++i) {
scanf ("%d%d", &u, &v);
e[i].nxt = head[u], e[i].v = v, head[u] = i;
}
// 缩点
for (int i = 1; i <= n; ++i)
if (!dfn[i]) tarjan (i);
for (int i = 1; i <= n; ++i)
for (int j = head[i]; j; j = e[j].nxt) {
if (c[e[j].v] == c[i]) continue;
add_c (c[i], c[e[j].v], c_node_cnt[c[e[j].v]]);
++ind[c[e[j].v]], has_outd[c[i]] = true;
// 细节！细节！！细节！！！
}
for (int i = 1; i <= c_cnt; ++i)
if (ind[i] == 0) {
add_c (0, i, c_node_cnt[i]);
ind[i] = 1;
}
// 作拓扑排序
sol_cnt[0] = 1;
topo ();
for (int i = 1; i <= c_cnt; ++i) {
// 统计方案，找最大解
if (!has_outd[i])
if (max_g_cnt < g_node_cnt[i]) // 现在找到的才是“最大”
sol = sol_cnt[i] % mod,
max_g_cnt = g_node_cnt[i];
else if (max_g_cnt == g_node_cnt[i]) // 或者二者相等？累加方案数。
sol = (sol_cnt[i] + sol) % mod;
}
cout << max_g_cnt << endl << sol;
return 0;
}再次感叹Tarjan老先生算法的奇妙。
发表回复