【51nod1299】监狱逃离（树形DP）

点此看题面

大致题意： 在一棵树中有\(N\)条边连接\(N+1\)个节点，现在已知这棵树上的\(M\)个节点，要求封住最少的节点，使这\(M\)个节点中的任意一个节点无法到达叶子节点，若能办到输出最少封住的节点数，若不能输出\(-1\)。

树形DP

这道题目的正解是树形\(DP\)（\(hl666\)大佬说用\(O(n^2m)\)的最小割也可以过这道题，不过这篇博客并不讨论这种做法，他能做出来是因为他是常数之神）。

树形\(DP\)，一般都将状态由子节点向父节点转移，这题当然也不例外。

我们可以用\(f\)数组来存储每一个节点的状态：

若\(f[i]=0\)，则说明该节点已被完全封死，相当于既不可能有犯人到达这里，也不可能从这里到达出口。

若\(f[i]=1\)，则说明可以从这个节点到达叶子节点。

若\(f[i]=2\)，则说明有犯人可以到达该节点。

每一次转移，我们可以用一个s[]数组来统计当前节点的子节点中\(f[son[i]]\)分别为\(0，1，2\)的次数，并依次进行分类讨论：

若当前节点有犯人，则需要在该节点的子节点中的每个可以到达叶子节点的节点上安排一个警卫。且\(f[x]=2\)（当前节点上有犯人，所以犯人可以到达该节点）。

若既有犯人可以到达该节点的某个子节点，又可以通过该节点的某个子节点到达叶子节点，这说明有犯人可以通过该节点逃出监狱，则需在这个节点安排一个警卫。且\(f[x]=0\)（当前节点安排了警卫，所以被完全封死）。

否则，如果该节点的某个子节点可以到达叶子节点，则说明该节点也可以到达叶子节点，因此\(f[x]=1\)。

否则，如果有犯人可以到达该节点的某个子节点，则说明犯人也可以到达该节点，因此\(f[x]=2\)。

如果以上情况皆不满足，这说明该节点是叶节点或其子节点全被封死，则特判其为叶子节点的情况，若其不是叶子节点则\(f[x]=0\)。

既然这样，就很容易进行动态规划了，具体代码如下：

代码

#include<bits/stdc++.h>

#define N 100000

using namespace std;

int n,m,ee=0,ans,a[N+5]={0},lnk[N+5]={0},OUT[N+5]={0},f[N+5]={0};

struct edge

{

	int to,nxt;

}e[2*N+5];

inline char tc()

{

	static char ff[100000],*A=ff,*B=ff;

	return A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++;

}

inline void read(int &x)

{

	x=0;int f=1;char ch;

	while(!isdigit(ch=tc())) if(ch=='-') f=-1;

	while(x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));

	x*=f;

}

inline void write(int x)

{

	if(x<0) putchar('-'),x=-x;

	if(x>9) write(x/10);

	putchar(x%10+'0');

}

inline void add(int x,int y)

{

	e[++ee]=(edge){y,lnk[x]},lnk[x]=ee,++OUT[x];

}

inline void dp(int x,int lst)//具体的DP过程

{

	int s[3];s[0]=s[1]=s[2]=0;//用s[]数组来统计当前节点子节点中各种状态的次数

	register int i;

	for(i=lnk[x];i;i=e[i].nxt)

		if(e[i].to^lst) dp(e[i].to,x),++s[f[e[i].to]];//先将其子节点进行DP，是一个递归的过程

	//接下来是分类讨论的过程

	if(a[x]) ans+=s[1],f[x]=2;//若当前节点有犯人

	else if(s[1]&&s[2]) ans++,f[x]=0;//若当前节点既能到达，又能出去

	else if(s[1]) f[x]=1;//若当前节点能出去

	else if(s[2]) f[x]=2;//若当前节点能到达

	else if(s[0]) f[x]=0;//若以上情况皆不满足且该节点不是叶节点

}

int main()

{

	register int i;int x,y,fst=-1;

	for(read(n),read(m),i=1;i<=n;++i)

		read(x),read(y),add(x,y),add(y,x);

	for(i=1;i<=m;++i)

	{

		read(x),a[x]=1;

		if(OUT[x]==1) return puts("-1"),0;//若有叶子节点关押犯人，则该犯人能直接逃脱

	}

	for(i=1;i<=n;++i)

		if(!(OUT[i]^1)) (fst==-1?fst=i:0),f[i]=1;//将叶子节点的状态初始化为1

	dp(fst,0);//从一个叶子节点开始DP

	return write(f[fst]==2?ans+1:ans),0;//特判该节点为2，即犯人可以到达的情况，由于当前节点是叶子节点，所以要在当前节点在安排一个警卫，答案加1

}

巴特西

【51nod1299】监狱逃离（树形DP）

树形DP

代码

最新文章

热门文章