#C241127A. [NOIP2022] 建造军营

动态规划 树形dp tarjan缩点
题目
发布日期:   2024-11-27
更新日期:   2024-11-29
文章字数:   2.5k
阅读时长:   10 分

#C241127A. [NOIP2022] 建造军营

标签（Label）

  • tarjan缩点
  • 树形dp
  • 动态规划

网址（Website）

P8867 [NOIP2022] 建造军营 - 洛谷

题目（Problem）

题目描述

A 国与 B 国正在激烈交战中，A 国打算在自己的国土上建造一些军营。

A 国的国土由 $n$ 座城市组成，$m$ 条双向道路连接这些城市，使得任意两座城市均可通过道路直接或间接到达。A 国打算选择一座或多座城市（至少一座），并在这些城市上各建造一座军营。

众所周知，军营之间的联络是十分重要的。然而此时 A 国接到情报，B 国将会于不久后袭击 A 国的一条道路，但具体的袭击目标却无从得知。如果 B 国袭击成功，这条道路将被切断，可能会造成 A 国某两个军营无法互相到达，这是 A 国极力避免的。因此 A 国决定派兵看守若干条道路（可以是一条或多条，也可以一条也不看守)，A 国有信心保证被派兵看守的道路能够抵御 B 国的袭击而不被切断。

A 国希望制定一个建造军营和看守道路的方案，使得 B 国袭击的无论是 A 国的哪条道路，都不会造成某两座军营无法互相到达。现在，请你帮 A 国计算一下可能的建造军营和看守道路的方案数共有多少。由于方案数可能会很多，你只需要输出其对 $1,000,000,007\left(10^{9}+7\right)$ 取模的值即可。两个方案被认为是不同的，当且仅当存在至少一 座城市在一个方案中建造了军营而在另一个方案中没有，或者存在至少一条道路在一个 方案中被派兵看守而在另一个方案中没有。

输入格式

第一行包含两个正整数 $n,m$，分别表示城市的个数和双向道路的数量。

接下来 $m$ 行，每行包含两个正整数 $u_{i},v_{i}$，描述一条连接 $u_{i}$ 和 $v_{i}$ 的双向道路。保证没有重边和自环。

输出格式

输出一行包含一个整数，表示建造军营和看守道路的方案数对 $1,000,000,007\left(10^{9}+ 7\right)$ 取模的结果。

样例 #1

样例输入 #1

2 1
1 2

样例输出 #1

5

样例 #2

样例输入 #2

4 4
1 2
2 3
3 1
1 4

样例输出 #2

184

样例 #3

见附加文件里的 $barrack/barrack3.in$ 和 $barrack/barrack3.ans$ 。

样例 #4

见附加文件里的 $barrack/barrack4.in$ 和 $barrack/barrack4.ans$ 。

提示

样例 1 解释

A 国有两座城市，一条道路连接他们。所有可能的方案如下：

  • 在城市 $1$ 建军营, 不看守这条道路;
  • 在城市 $1$ 建军营, 看守这条道路;
  • 在城市 $2$ 建军营, 不看守这条道路;
  • 在城市 $2$ 建军营, 看守这条道路;
  • 在城市 $1,2$ 建军营, 看守这条道路。

数据规模与约定

对所有数据，保证 $1 \leq n \leq 5 \times 10^5$，$n - 1 \leq m \leq 10^6$，$1 \leq u_i, v_i \leq n$，$u_i \neq v_i$。

各测试点的信息如下

测试点编号$n \leq $$m \leq $特殊条件
$1 \sim 3$$8$$10$无
$4 \sim 7$$16$$25$无
$8 \sim 9$$3000$$5000$无
$10 \sim 11$$5 \times 10^5$$10^6$特殊性质 $\mathrm{A}$
$12 \sim 14$$5 \times 10^5$$10^6$$m = n - 1$
$15 \sim 16$$5 \times 10^5$$10^6$$m = n$
$17 \sim 20$$5 \times 10^5$$10^6$无

特殊性质 $\mathrm{A}$：保证 $m=n-1$ 且第 $i$ 条道路连接城市 $i$ 与 $i+1$。

题解（Solution）

先整理一下需要满足的条件：

  1. 枚举每个城市是否建军营；
  2. 断一条边使得军营仍然联通；
  3. 可以保护若干条边；

容易发现只把军营建在一个强连通分量内，那么一条边都不用保护，那么自然就会考虑到树的情况。

计算方案数，肯定是动态规划，转成一棵树之后，就需要考虑树形 $\text{dp}$ ，如果两个点里面都要建造军营，那么这两个点路径上所有的桥都要保护，否则 $\text{B}$ 国就可以攻击这条路，而不再他们路径上的边或者是非桥边可以任选保护与否。

设 $f_{x}$ 表示以 $x$ 为根的子树的方案数有多少，发现这种设计情况太多，我们就加入一个状态 $g_x$ ，记录当前子树里面没有军营时的方案数，并且强制限制 $f_x$ 记录的是子树内有军营时的方案数。发现这样其实还是不够，因为子树内有军营有两种情况：1. 只有这棵子树内有军营；2. 子树外还有军营。

如果只有这棵子树内有军营，我们只需要在子树内计算出答案就好了，但是如果在子树外有军营，我们就需要限制从子树的军营到当前的根 $x$ 的路径上的所有边都需要被保护。

那么直接钦定 $f_x$ 表示以 $x$ 为根的子树内有军营且外面也有军营的方案数有多少，并且增加一个 $h_x$ 表示军营只在以 $x$ 为根的子树中，且军营路径必须经过 $x$ 的方案数。

缩出来的点包含的点的个数 $siz$ 以及边的条数 $edg$ 会影响到这个点的方案数，容易发现初始状态有：
$$
f_x = (2^{siz_x}-1)\times 2^{edg_x}
$$
减一是因为 $x$ 中必须选一个军营，不能没有。再考虑 $g_x$ ：
$$
g_x = 2^{edg_x}
$$
每条边都有保护和不保护两个状态。

这样的话，初始值就设出来了，我们在考虑枚举情况来转移：
$$
f_x = f_x \times f_y + g_x \times f_y + f_x\times g_x\times2\\
g_x = g_x \times g_y \times 2
$$
对于 $f_x$ ，转移就是分别枚举子树内部有没有军营，一共四种情况，注意取到 $g_y$ 的时候要乘 $2$ ，因为不选 $y$ 子树中的点作为军营时，子树 $y$ 到根节点那条便也可以随便选保护与否。

最后对于每棵子树，它的答案就是自己的方案数$\times$剩下的边随便选的方案数。式子里面的 $s_x$ 表示的是该节点子树内的边的数量，$cnt$ 表示强连通分量的个数。
$$
ans = \sum_{x=1}^{cnt} f_x\times 2^{m-s_x}
$$
剩下唯一的问题就是当我们固定点 $x$ 必须经过的时候 $g_x\times f_y$ 这种情况可能会计算出当前只有 $y$ 一棵子树选择了军营而其他都没有选的情况，这个时候所有军营只在 $y$ 的子树内，那么必须保护的路径一定不经过 $x$ ，那么这种情况需不需要删去呢？不需要。

如果当前计算了这种情况，那么相当于计算了所有军营在子树 $y$ 内且 $x\to y$ 这条边要选的情况，那么我们就只用计算所有军营在子树 $y$ 且 $x\to y$ 不选的情况，所以，最后的式子：
$$
ans = \sum_{x=1}^{cnt} f_x\times 2^{m-s_x-1}
$$
多减的 $1$ 就是去掉选 $x\to y$ 的贡献，因为只用计算这条边不选的贡献就好了。特别的，因为根没有父节点，没有 $x\to y$ 这条边，那么就没有选不选 $x\to y$ 的问题了，需要特判一下。

时间复杂度： $O(n+m)$ 。

代码（Code）

100分
#include<bits/stdc++.h>
#include<vector>
#include<stack>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a,n) For(i,1,n) cerr<<a[i]<<' ';cerr<<'\n';
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x; 
}template<typename G>
void write(G x){
	if(x<0) putchar('-'), write(-x);
	else if(x<=9) putchar('0'+x);
	else write(x/10), putchar(x%10+'0');
}constexpr int inf = 0x3f3f3f3f3f3f3f;
constexpr int mod = 1e9+7;
constexpr int N = 501234;
bool ST;
inline void add(int &x,int y){if((x+=y)>=mod)x-=mod;}
inline void mul(int &x,int y){x=x*y%mod;}
int fac[N],inv[N];
inline int ksm(int x,int k=mod-2){
	int res=1;while(k){
		if(k&1) mul(res,x);
		mul(x,x), k>>=1;
	}return res;
}

vector<int> e[N],ft[N];
int n,m,ans;

int dfn[N],low[N],t;
stack<int> st;
int ttt=0;
int scc[N],cnt,siz[N],edg[N];
void tarjan(int x,int fa){
	dfn[x]=low[x]=++t, st.emplace(x);
	for(auto y:e[x]) if(y^fa){
		if(!dfn[y]) tarjan(y,x), low[x]=min(low[x], low[y]);
		else low[x] = min(low[x], dfn[y]);
	}
	if(low[x]==dfn[x]){
		scc[x] = ++cnt;
		siz[cnt]++;
		while(x^st.top()){
			ttt++;
			scc[st.top()] = cnt;
			siz[cnt]++, st.pop();
		}st.pop();
	}
}

int f[N],g[N];
void dfs(int x,int fa){
	f[x] = (ksm(2,siz[x])-1) * ksm(2,edg[x])%mod, 
	g[x] = ksm(2,edg[x]);
	for(auto y:ft[x]) if(y^fa){
		dfs(y,x);
		edg[x] += edg[y]+1;
		f[x] = (g[y]*2*f[x]%mod + f[y]*g[x]%mod + f[y]*f[x]%mod)%mod;
		g[x] = g[x]*g[y]*2%mod;
	}
	for(auto y:ft[x]) if(y^fa) 
		add(f[x], mod-f[y]*g[x]%mod*ksm(g[y]*2%mod)%mod);
}

void Solve(){
	n=rd(),m=rd();For(i,1,m){
		int x=rd(), y=rd();
		e[x].emplace_back(y);
		e[y].emplace_back(x);
	}tarjan(1,0);
	For(x,1,n) for(auto y:e[x]){
		int i=scc[x], j=scc[y];
		if(i^j) ft[i].emplace_back(j);
		else edg[scc[x]]++;
	}For(i,1,cnt) assert(edg[i]%2==0),edg[i]>>=1;
	dfs(1,0);
	add(ans, f[1]);
	For(i,2,cnt) add(ans, f[i]*ksm(2,m-edg[i])%mod);
	write(ans), putchar('\n');
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int Tt=1;double Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
文章作者: WolfDeer
文章链接: https://wolfdeer62456.github.iohttps://wolfdeer62456.github.io/2024/11/27/C241127A-NOIP2022-%E5%BB%BA%E9%80%A0%E5%86%9B%E8%90%A5/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 WolfDeer !
动态规划 树形dp tarjan缩点
赏
  目录