1299?監獄逃離 題目來源：?Codility 基準時間限制：1?秒 空間限制：131072?KB 分值:?320?難度：7級算法題 ?收藏 ?關注 監獄有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

以任意一個葉子節點作為根節點

mark[u]=0:以u為根的子樹的犯人能到達u，但不存在從u到葉子的路徑
mark[u]=1:以u為根的子樹中的犯人不能到達u，但存在從u到葉子的路徑
mark[u]=2:以u為根的子樹中的犯人不能到達u，且不存在從u到葉子的路徑

u有犯人，子節點不能存在通往葉子的路徑
u沒有犯人，如果子節點有犯人能到u且有路徑從子節點到葉子,封鎖u

根節點狀態為0，則封鎖根節點

#include<cstdio> #include<string.h> #include<algorithm> using namespace std; const int INF = 0x3f3f3f3f; const int MX = 2e5 + 5; struct Edge{int v,nxt; }E[MX*2]; int head[MX],tot; int son[MX][3],mark[MX],p[MX],IN[MX],ans; void init(){memset(head,-1,sizeof(head));tot=0; } void add(int u,int v){E[tot].v=v;E[tot].nxt=head[u];head[u]=tot++;IN[v]++; } void dfs(int u,int fa){if(IN[u]==1&&fa!=-1){mark[u]=1;return;}for(int i=head[u];~i;i=E[i].nxt){int v=E[i].v;if(v==fa) continue;dfs(v,u);son[u][mark[v]]++;}//if(u==1) printf("%d\n",son[u][1]);if(p[u]) ans+=son[u][1]; //有犯人,封鎖所有可以通往葉子的兒子else if(son[u][0]&&son[u][1]){//有犯人能到u且有路徑從u到葉子,封鎖uans++;mark[u]=2;}else if(son[u][0]) mark[u]=0;else if(son[u][1]) mark[u]=1;else mark[u]=2; } int main(){int n,m;//freopen("in.txt","r",stdin);scanf("%d%d",&n,&m);init();for(int i=1,u,v;i<=n;i++) {scanf("%d%d",&u,&v);add(u,v);add(v,u);}int flag=1;for(int i=1,u;i<=n;i++){scanf("%d",&u);if(IN[u]==1){printf("-1\n");flag=0;}p[u]=1;}if(flag){ans=0;for(int i=0;i<=n;i++) if(IN[i]==1){dfs(i,-1);if(mark[i]==0) ans++;break;}printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的51nod-1299 监狱逃离（贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

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