題意：監(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。

這個最小割的模型十分明顯，但是n<=200000讓我沒敢寫，評論里面一堆人卡過了。。
正解是一個思路清奇的dp。。沒見過dp這么寫的。
設(shè)f[x]表示x的狀態(tài)，取值有三種。
0：這個點為根的子樹中所有的逃犯都無法到達(dá)這個點，且不存在一條從這點到葉子節(jié)點的路徑。
1：這個點為根的子樹中所有的逃犯都無法到達(dá)這個點，但存在一條從這點到葉子節(jié)點的路徑。
2：這個點為根的子樹中所有的逃犯有可能到達(dá)這個點，且不存在一條從這點到葉子節(jié)點的路徑。
首先如果x這個點有囚犯，那么我肯定不能讓x能到達(dá)他子樹中狀態(tài)為1的點，那么就把答案加上子樹中狀態(tài)為1的點，x的狀態(tài)變?yōu)?。
如果以x為根的子樹既有狀態(tài)為1又有狀態(tài)為2的點，那么狀態(tài)為2的兒子就可以通過x向外面逃走，所以這個也要被鎖死。
否則的情況就比較好處理了，如果子樹中有0那么x為0，否則子樹中是什么x就是什么。
最后如果根的狀態(tài)為2，那么明顯根也要放一個。
數(shù)據(jù)沒出-1的情況。。

#include<cstdio> #include<algorithm> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=2e5+5; int n,m; int head[N],next[N],go[N],d[N]; int f[N],s[5],bz[N],tot,ans; inline void add(int x,int y) {go[++tot]=y;next[tot]=head[x];head[x]=tot; } inline void dfs(int x,int fa) {int s[3];memset(s,0,sizeof(s));for(int i=head[x];i;i=next[i]){int v=go[i];if (v!=fa){dfs(v,x);s[f[v]]++;}}if (bz[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() {scanf("%d%d",&n,&m);fo(i,1,n){int x,y;scanf("%d%d",&x,&y);x++,y++;add(x,y),add(y,x);d[x]++,d[y]++;}fo(i,1,m){int x;scanf("%d",&x);x++;bz[x]=1;}fo(i,1,n+1)f[i]=1;fo(i,1,n+1){if (d[i]==1){dfs(i,i);if (f[i]==2)ans++;printf("%d\n",ans);return 0;}} }

總結(jié)

以上是生活随笔為你收集整理的51nod 1299 监狱逃离 树形dp/最小割的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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