監(jiān)獄有N條道路連接N + 1個交點，編號0至N，整個監(jiān)獄被這些道路連在一起（任何2點之間都有道路），人們通過道路在交點之間走來走去。其中的一些交點只有一條路連接，這些點是監(jiān)獄的出口。在各個交點中有M個點住著犯人(M <= N + 1)，剩下的點可以安排警衛(wèi)，有警衛(wèi)把守的地方犯人無法通過。給出整個監(jiān)獄的道路情況，以及犯人所在的位置，問至少需要安排多少個警衛(wèi)，才能保證沒有1個犯人能夠逃到出口，如果總有犯人能夠逃出去，輸出-1。

如上圖所示，點1,6 住著犯人，0,4,5,7,8是出口，至少需要安排4個警衛(wèi)。
Input

第1行：2個數(shù)N, M中間用空格分隔，N表示道路的數(shù)量，M表示犯人的數(shù)量(1<= N <= 100000, 0 <= M <= N + 1)。
之后N行：每行2個數(shù)S, E中間用空格分隔，表示點編號為S的點同編號為E的點之間有道路相連。(0 <= S, E <= N)。
之后的M行，每行1個數(shù)Pi，表示編號為Pi的點上有犯人。

Output

輸出1個數(shù)對應最少需要多少警衛(wèi)才能不讓犯人逃出監(jiān)獄。

Input示例

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

Output示例

4

ORZ ，學長在網(wǎng)絡流專題里放這么一道毒瘤題，20w個點，他說可以用網(wǎng)絡流遛一遛。。。。 我自己寫的網(wǎng)絡流交了十多發(fā)才卡過去。。。。
ヽ(ー_ー)ノ

正解應該是樹形DP，那時候并不了解樹形DP。。 看題解都理解了好久。。。。。
這道題跟UVA1218的狀態(tài)轉移方程有一些相似。有興趣的可以去看一哈。 也挺有意思的
**

解題思路

**

他給出的是一棵樹，求的是最小花費問題，圖上的最小花費一般是最短路，網(wǎng)絡流，或者DP問題了。 這里由于20w個點，網(wǎng)絡流應該首先被pass掉（實在不行也可以試一發(fā)，暴力出奇跡）。
這題看不出跟最短路有啥關系，我們應該往樹形DP的方向去想。
我們來考慮一下，放完警衛(wèi)后，這個樹形圖上每個點的狀態(tài)會是怎么樣的。
狀態(tài)一. 這個點的子樹上的逃犯逃不到這個點，這個點也無法通向的它子樹的葉子節(jié)點
狀態(tài)二. 這個點的子樹上的逃犯逃不到這個點，這個點有通向其葉子節(jié)點的路徑
狀態(tài)三. 這個點的子樹上的逃犯能到達這個節(jié)點，這個節(jié)點無法通向其子樹的葉子節(jié)點。
除此之外，如果這個圖擁有其他狀態(tài)的點，那么絕對不合法。
這里在我們更新子節(jié)點的時候不用考慮這個節(jié)點父親節(jié)點的狀況，因為父親節(jié)點的狀態(tài)就是由子節(jié)點唯一確定的。
狀態(tài)很少，所以我們可以很輕易的枚舉所有狀態(tài)。 由此可以寫出dp數(shù)組的定義

int dp[100005]; // 0表示子節(jié)點的逃犯無法到達這個節(jié)點，該節(jié)點可通向葉子結點。 既葉子節(jié)點的初始狀態(tài) // 1表示 表示子節(jié)點逃犯無法到達這個節(jié)點，該節(jié)點不可通向葉子結點 // 2表示該節(jié)點的子樹的有逃犯可以到達該節(jié)點，且該節(jié)點不可以通向葉子節(jié)點 囚犯所在的節(jié)點都會是這個狀態(tài)

怎么轉移呢。 分類討論一下，判斷出每種狀態(tài)的優(yōu)先級不停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表示子節(jié)點的逃犯無法到達這個節(jié)點，該節(jié)點可通向葉子結點。 既葉子節(jié)點的初始狀態(tài) // 1表示 表示子節(jié)點逃犯無法到達這個節(jié)點，該節(jié)點不可通向葉子結點 // 2表示該節(jié)點的子樹的有逃犯可以到達該節(jié)點，且該節(jié)點不可以通向葉子節(jié)點 囚犯所在的節(jié)點都會是這個狀態(tài) 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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。