[51nod1299]监狱逃离 树形DP || 20w个点的网络流最小割ORZ

监狱有N条道路连接N + 1个交点，编号0至N，整个监狱被这些道路连在一起（任何2点之间都有道路），人们通过道路在交点之间走来走去。其中的一些交点只有一条路连接，这些点是监狱的出口。在各个交点中有M个点住着犯人(M <= N + 1)，剩下的点可以安排警卫，有警卫把守的地方犯人无法通过。给出整个监狱的道路情况，以及犯人所在的位置，问至少需要安排多少个警卫，才能保证没有1个犯人能够逃到出口，如果总有犯人能够逃出去，输出-1。

如上图所示，点1,6 住着犯人，0,4,5,7,8是出口，至少需要安排4个警卫。
Input

第1行：2个数N, M中间用空格分隔，N表示道路的数量，M表示犯人的数量(1<= N <= 100000, 0 <= M <= N + 1)。
之后N行：每行2个数S, E中间用空格分隔，表示点编号为S的点同编号为E的点之间有道路相连。(0 <= S, E <= N)。
之后的M行，每行1个数Pi，表示编号为Pi的点上有犯人。

Output

输出1个数对应最少需要多少警卫才能不让犯人逃出监狱。

Input示例

8 2
0 1
1 2
2 3
3 4
3 5
2 6
6 8
6 7
1
6

Output示例

4

ORZ ，学长在网络流专题里放这么一道毒瘤题，20w个点，他说可以用网络流遛一遛。。。。 我自己写的网络流交了十多发才卡过去。。。。
ヽ(ー_ー)ノ

正解应该是树形DP，那时候并不了解树形DP。。 看题解都理解了好久。。。。。
这道题跟UVA1218的状态转移方程有一些相似。有兴趣的可以去看一哈。 也挺有意思的
**

解题思路

**

他给出的是一棵树，求的是最小花费问题，图上的最小花费一般是最短路，网络流，或者DP问题了。 这里由于20w个点，网络流应该首先被pass掉（实在不行也可以试一发，暴力出奇迹）。
这题看不出跟最短路有啥关系，我们应该往树形DP的方向去想。
我们来考虑一下，放完警卫后，这个树形图上每个点的状态会是怎么样的。
状态一. 这个点的子树上的逃犯逃不到这个点，这个点也无法通向的它子树的叶子节点
状态二. 这个点的子树上的逃犯逃不到这个点，这个点有通向其叶子节点的路径
状态三. 这个点的子树上的逃犯能到达这个节点，这个节点无法通向其子树的叶子节点。
除此之外，如果这个图拥有其他状态的点，那么绝对不合法。
这里在我们更新子节点的时候不用考虑这个节点父亲节点的状况，因为父亲节点的状态就是由子节点唯一确定的。
状态很少，所以我们可以很轻易的枚举所有状态。 由此可以写出dp数组的定义

int dp[100005]; // 0表示子节点的逃犯无法到达这个节点，该节点可通向叶子结点。 既叶子节点的初始状态 // 1表示 表示子节点逃犯无法到达这个节点，该节点不可通向叶子结点 // 2表示该节点的子树的有逃犯可以到达该节点，且该节点不可以通向叶子节点 囚犯所在的节点都会是这个状态

怎么转移呢。 分类讨论一下，判断出每种状态的优先级不停if else即可。。。。。。。

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<queue> #include<cmath> #include<limits> #include<map> #include<set> #include<stack> #include<string> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define fuck(x) cout<<"["<<x<<"]"<<endl #define mem(a,b) memset(a,b,sizeof a); class edges { public:int u,v,next; }; edges edge[100005*2]; int tot=0; int head[100005]; int ans=0; void init() {mem(head,-1);tot=0;ans=0; } void add(int u,int v) {edge[tot].u=u; edge[tot].v=v;edge[tot].next=head[u];head[u]=tot; tot++; } int people[100005]; int dp[100005]; // 0表示子节点的逃犯无法到达这个节点，该节点可通向叶子结点。 既叶子节点的初始状态 // 1表示 表示子节点逃犯无法到达这个节点，该节点不可通向叶子结点 // 2表示该节点的子树的有逃犯可以到达该节点，且该节点不可以通向叶子节点 囚犯所在的节点都会是这个状态 void dfs(int root,int per) {int s[3]={0,0,0};for(int i=head[root];i!=-1;i=edge[i].next){int v=edge[i].v;if(v==per)continue;dfs(v,root);s[dp[v]]++;}if(people[root]){dp[root]=2;ans+=s[0];}else if(s[2]&&s[0]){ans++;dp[root]=1;}else if(s[0]){dp[root]=0;}else if(s[2]){dp[root]=2;}else if(s[1]){dp[root]=1;} } int du[100005]; int main() {int n,m;scanf("%d %d",&n,&m);init();for(int i=1;i<=n;i++){int u,v;scanf("%d %d",&u,&v);add(u,v);add(v,u);du[u]++;du[v]++;}for(int i=1;i<=m;i++){int root;scanf("%d",&root);people[root]=1;}for(int i=1;i<n;i++){if(du[i]==1){dfs(i,-1);if(dp[i]==2)ans++;cout<<ans<<endl;break;}}return 0; }

总结

以上是生活随笔为你收集整理的[51nod1299]监狱逃离 树形DP || 20w个点的网络流最小割ORZ的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。