【题解】[CCO2021] Bread First Search

本文主要是介绍【题解】[CCO2021] Bread First Search，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题意：给定一个图，求最少需要加入多少条边使得图的 \(BFS\) 顺序可能为 \(1\sim N\)。

神仙题，首先得发现这是个线性 DP，并写出状态和方程，做到这里这题就完成了一半。

状态，我们定义 \(f_i\) 表示节点 \(1\sim i\)​ 的子图的答案。

转移 \(f_i + val(i+1, j) \to f_j\)，条件为节点 \(1\sim i\) 和节点 \((j + 1)\sim n\) 之间没有边。

其中 \(val(i,j)\)​ 表示 \((i + 1)\sim j\) 中与 \(1\sim i\)​ 中节点有边的节点数。

不难发现 check 和 val 本质上是相同的，我们只用预处理 \(s_{i,j}\) 表示点 \(1\sim j\) 中与点 \(1\sim i\) 中节点有边的节点数即可。

其中 $s_i $ 是在 \(s_{i - 1}\) 的基础上改动几个，直接用可持久化线段树优化即可。

但是我们转移还是 \(N^2\) 的，考虑优化。根据套路，这题既没有斜率也无法单调队列，只有决策单调性。

打个表，或者感性理解一下，就能发现这个方程确实有决策单调性。直接队列优化即可。

时间复杂度 \(\mathcal{O}(N\log ^2 N)\) ，空间 \(\mathcal{O}(N\log N)\)​。以下是 \(N^2\) 的算法。

#define N 5005

int n, m, f[N], s[N][N], g[N];
int main(){
	//int T = read();while(T--)solve();
	n = read(), m = read();
	rp(i, m){
		int x = read(), y = read();
		if(x > y)swap(x, y);
		s[x][y] = 1;
	}
	rp(i, n)rp(j, n)
			s[i][j] = (s[i][j] | (s[i - 1][j] - s[i - 1][j - 1])) + s[i][j - 1];
	memset(f, 0x3f, sizeof(f));
	f[1] = 0;
	rp(i, n - 1){
		rep(j, i + 1, n){
			int cur = f[i] - s[i][j] + s[i][i] + j - i;
			if(!(s[i][n] - s[i][j]) && cur <= f[j])
				f[j] = cur, g[j] = i;
		}
	}
	rp(i, n - 1)assert(g[i] <= g[i + 1]);
	printf("%d\n", f[n]);
	return 0;
}

这篇关于【题解】[CCO2021] Bread First Search的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！