[USACO18JAN] Cow at Large G (dfs)

题目大意：有一只狐狸从给定的S点开始逃跑(出发)，向叶节点移动以逃离这棵树，叶节点可能出现农民去抓捕狐狸，当农民和狐狸出现在同一个节点的时候，狐狸会被抓住，农民和狐狸移动速度相同，求抓捕狐狸所需要的最少农民数

显然，当 u 节点的子树内存在一叶节点 i 满足deep[i]-deep[u]<=deep[u]时，说明 u 的子树能被守住

即农民从 i 移动到 u 所需要的时间小于等于狐狸从出发点移动到 u 的时间

第一遍dfs预处理出每个节点的深度dep，以及每个节点的子树内深度最小的叶节点的深度mindep(代码中简化为mi)

第二遍dfs求答案，只要某个节点能被其子树内某个叶节点守住，那么它子树内其它节点就不用考虑了，return 1

但并不能从S点直接开始第二个dfs，而是从S点直接连接的所有节点开始，因为狐狸和农民移动速度一样，如果按之前的方法，狐狸可能会往相反方向跑，导致农民无法追上狐狸

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N 100005

 #define inf 0x3f3f3f3f

 #define maxn 1000010

 using namespace std;

 //re

 int n,S,cte;

 int head[N],dep[N],mi[N],inc[N];

 struct Edge{int to,nxt;}edge[N*];

 void ae(int u,int v){

     cte++;edge[cte].to=v,inc[v]++;

     edge[cte].nxt=head[u],head[u]=cte;

 }

 void dfs1(int u,int fa)

 {

     if(inc[u]==) {mi[u]=dep[u];return;}

     for(int j=head[u];j;j=edge[j].nxt){

         int v=edge[j].to;

         if(v==fa) continue;

         dep[v]=dep[u]+;

         dfs1(v,u);

         mi[u]=min(mi[u],mi[v]);

     }

 }

 int dfs2(int u,int fa)

 {

     int ans=;

     if(mi[u]-dep[u]<=dep[u])

         return ;

     for(int j=head[u];j;j=edge[j].nxt){

         int v=edge[j].to;

         if(v==fa) continue;

         ans+=dfs2(v,u);

     }

     return ans;

 }

 int main()

 {

     scanf("%d%d",&n,&S);

     int x,y,ans=;

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

         scanf("%d%d",&x,&y),ae(x,y),ae(y,x);

     memset(mi,0x3f,sizeof(mi));

     dfs1(S,-);

     for(int j=head[S];j;j=edge[j].nxt){

         int v=edge[j].to;

         ans+=dfs2(v,S);

     }printf("%d\n",ans);

     return ;

 }

巴特西

[USACO18JAN] Cow at Large G (dfs)

最新文章

热门文章