题解 P4186 【[USACO18JAN]Cow at Large G】

bessie_goes_moo · 2019-08-23 20:06:17 · 题解

楼上众神仙写的都是正解，我的是在模拟赛瞎糊弄的（隔了一年前打的，今天又刷到了，然鹅我还是很菜，写的如下玄学算法）

大致思路就是让bessie向叶子跑，如果跑出去了在那里放个守卫重来一次，所以复杂度是O(Ans*N)的，但实际跑出来还是个玄学时效

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int Q[maxn],son[2*maxn],lnk[maxn],nxt[2*maxn],ANS[maxn],s,du[maxn],tot,n;
bool vis[maxn],Bissie[maxn];
inline int read(){
    int red=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') red=red*10+ch-48,ch=getchar();
    return red*f;
}
void add_e(int x,int y){
    son[++tot]=y,nxt[tot]=lnk[x],lnk[x]=tot,du[y]++;
}
void BFS(){
    memset(vis,0,sizeof vis);
    int hed=0,til=0;
    for(int i=1;i<=ANS[0];i++) Q[++til]=ANS[i],Bissie[ANS[i]]=0,vis[ANS[i]]=1;
    Q[++til]=s,vis[s]=1,Bissie[s]=1;
    while(hed<til){
        int x=Q[++hed];
        for(int j=lnk[x];j;j=nxt[j])
        if(!vis[son[j]]){ 
            if(du[son[j]]==1&&Bissie[x]){
                ANS[++ANS[0]]=son[j];BFS();return;
            }
            vis[son[j]]=1,Q[++til]=son[j],Bissie[son[j]]=Bissie[x];
        }
    }
}
int main(){
    freopen("atlarge.in","r",stdin);
    freopen("atlarge.out","w",stdout);
    n=read(),s=read();
    for(int i=1;i<n;i++){int x=read(),y=read();add_e(x,y),add_e(y,x);}
    if(du[s]==1){ANS[++ANS[0]]=s;}
    BFS();
    printf("%d\n",ANS[0]);
    return 0;
}