OI

洛谷题库 P2272 [ZJOI2007]最大半连通子图 题解与思路重现

洛谷题库 P2272 [ZJOI2007]最大半连通子图

有感而发，今晚一定先写篇题解。这可是我AC的第一道紫题！

题目中说半连通子图指的是对于图G(V,E)G(V, E)，∀u,v∈V\forall u, v \in V 有 u→vu \to v 或者 v→uv \to u。当时我对于“或”的理解是异或，也就是二者不能同时存在。

——那这题基本没法做啊？比如我们作一次DFS，搜索的时候光是找到一条横叉边，就已经让人头疼怎么处理；更别说还要判环，还要找“最大”的半连通子图。

但有一点是可以确定的——当图中可以将环处理掉时，“半连通子图”将会是一条链。易知对于链上的节点u,vu, v (u是v的祖先)，都有u→vu \to v。

中午憋不住了，问了已经AC的lty大佬。他告诉我这是可兼或。果然！于是我们自然想到，对于每一个SCC（强连通分量），必然满足“半连通子图”的定义。

所以我们立刻使用Tarjan执行缩点。完成后将得到一张DAG（有向无环图），这时就可以通过拓扑排序，累加以其结尾的链的个数了。我自然写出一份爆零代码：

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  63. 63
  64. 64
  65. 65
  66. 66
  67. 67
  68. 68
  69. 69
  70. 70
  71. 71
  72. 72
  73. 73
  74. 74
  75. 75
  76. 76
  77. 77
  78. 78
  79. 79
  80. 80
  81. 81
  82. 82
  83. 83
  84. 84
  85. 85
  86. 86
  87. 87
  88. 88
  89. 89
  90. 90
  91. 91
  92. 92
  93. 93
  94. 94
  95. 95
  96. 96
  97. 97
  98. 98
  99. 99
  100. 100
  101. 101
  102. 102
  103. 103
  104. 104
  105. 105
  106. 106
  107. 107
  108. 108
  109. 109
  110. 110
  111. 111
  112. 112
  113. 113
  114. 114
  115. 115
  116. 116
  117. 117
#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;
}

R53023327 记录详情

又是TLE又是MLE又是WA的。

仔细一看，存在很大问题：

  • 先进行一次拓扑排序找“方案数”，又用BFS找最大解。而且为了不漏解，BFS遍历了每一条可能的路径（甚至不是按照节点层数扩展的）（粗算时间复杂度是O(∏d+(v))O(\prod d^+(v))，即每个点的出度的乘积），显然直接爆时间；
  • 建缩点过后新图的代码写错了（细节啊！）。

将这些细枝末节的地方改正之后，再交，仍然爆零。并且查看输出信息发现，第一行（输出最大链长度）没有问题，但第二行（输出方案数）全部不正确。

冥思苦想了好久……修改了一些细节提交，仍然不正确。无奈，只得去题解板块寻找与我的相同的思路。但令人惊奇的是，这些题解求答案时，无一例外都有这个转移方程：

设以编号为ii的SCC为结尾的最长链的条数为g[i]g[i]，长度为f[i]f[i]，有编号为jj的SCC，j→ij \to i，则有

{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]).\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’ 是 GG 所有半连通子图中包含节点数最多的，则称G’G’是GG的最大半连通子图。”

看来连题都读错了。它求的是“最长链数量”，而我求的是“以第ii个SCC结尾的链的总方案数”。这样一来，转移方程也就可以理解了。现有方案更优，则直接按照现有方案信息转移；若同样优秀，则方案数累加。

我们再倒回去说说使用拓扑排序求解、转移答案的正确性。因为在拓扑排序中会记录每个点的入度，每遍历一条边e<u,v>e<u, v>都会将vv入度减11，当且仅当d−(v)=0d^-(v) = 0时才会将vv入队，扩展节点。则易知这样可以保证每一个节点从入边获得最优解。

（哦对了，拓扑之前要去重边。）

时间复杂度O(∣V∣+∣E∣)\mathbf{O}(|V| + |E|)。AC代码如下：

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  63. 63
  64. 64
  65. 65
  66. 66
  67. 67
  68. 68
  69. 69
  70. 70
  71. 71
  72. 72
  73. 73
  74. 74
  75. 75
  76. 76
  77. 77
  78. 78
  79. 79
  80. 80
  81. 81
  82. 82
  83. 83
  84. 84
  85. 85
  86. 86
  87. 87
  88. 88
  89. 89
  90. 90
  91. 91
  92. 92
  93. 93
  94. 94
  95. 95
  96. 96
  97. 97
  98. 98
  99. 99
  100. 100
  101. 101
  102. 102
  103. 103
  104. 104
  105. 105
  106. 106
#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;
}

R53053837 记录详情

再次感叹Tarjan老先生算法的奇妙。

  • 2021年7月14日

Tags:

You may also like...

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

成都外国语学校高二 OIer。喜欢搞些杂七杂八的小项目。常去骑车。复健中，脚力已不如前。

一言(ひとこと)

暫し空に祈りて 愛を断て

分类目录