USACO 2018 December Contest Platinum T3: The Cow Gathering

题目大意

奶牛们从世界各地聚集起来参加一场大型聚会。总共有 N 头奶牛, N−1 对奶牛互为朋友。每头奶牛都可以通过一些朋友关系认识其他每头奶牛。

她们玩得很开心,但是现在到了她们应当离开的时间了,她们会一个接一个地离开。她们想要以某种顺序离开,使得只要至少还有两头奶牛尚未离开,所有尚未离开的奶牛都还有没有离开的朋友。此外,由于行李寄存的因素,有 M 对奶牛 (ai​,bi​) 必须满足奶牛 ai​ 要比奶牛 bi​ 先离开。注意奶牛 ai​ 和奶牛 bi​ 可能是朋友,也可能不是朋友。

帮助奶牛们求出,对于每一头奶牛,她是否可以成为最后一头离开的奶牛。可能会发生不存在满足上述要求的奶牛离开顺序的情况。

题目分析

从“总共有 N 头奶牛, N−1 对奶牛互为朋友”可知,合法情况下(有答案),这N头奶牛的关系构成了一棵树。若是构成环或其他形态,则该题答案均为0。

以下分析建立在 “这N头奶牛的关系构成了一棵树” 这样的合法情况下。

若没有行李寄存的限制,明显,每头牛都可以成为最后离开的牛。

而若有一对限制(a, b),a 要比奶牛 b​ 先离开,那么这样的话,以b为根的情况下,a的子树中的点 因为要比a先离开,所以他们比不会成为剩下两个点中的一个,也就是说,他们的答案都为0。

我们将a打上标记。

观察到,若 点x 为一可行点(答案为1),则把 x 点提为根,从根往下dfs,碰到有标记的点立即返回,那么它能到达的所有点都为可行点。

所以我们只需通过一遍拓扑排序找到一个可行点后dfs即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN=1e5+10;
 4 
 5 struct Edge{
 6     int to,nxt;
 7 }e[MAXN<<1];
 8 int cnt,head[MAXN];
 9 inline void add_edge(int u,int v){
10     e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
11 }
12 int n,m,rt;
13 int ind[MAXN];
14 bool vis[MAXN],f[MAXN];
15 vector<int> lim[MAXN];
16 queue<int> q;
17 inline int Solve(){
18     int tot=0;
19     while(!q.empty()){
20         int x=q.front();q.pop();
21         ++tot;
22         if(ind[x]!=1){
23             if(!ind[x]) return x;
24             //for(int i=1;i<=n;++i)
25             //    printf("0\n");
26             //exit(0);
27         }
28         for(int i=head[x],y;i;i=e[i].nxt){
29             y=e[i].to;
30             --ind[y];++tot;
31             if(ind[y]==1) q.push(y);
32         }
33         for(int i=0,y;i<(int)lim[x].size();++i){
34             y=lim[x][i];
35             --ind[y];++tot;
36             if(ind[y]==1) q.push(y);
37         }
38     }
39     if(tot!=n){
40         for(int i=1;i<=n;++i)
41                 printf("0\n");
42             exit(0);
43     }
44 }
45 inline void dfs(int x,int fa=0){
46     f[x]=1;
47     for(int i=head[x],y;i;i=e[i].nxt){
48         y=e[i].to;
49         if(y!=fa&&!vis[y])
50             dfs(y,x);
51     }
52 }
53 int main(){
54     scanf("%d%d",&n,&m);
55     for(int i=1,u,v;i<n;++i){
56         scanf("%d%d",&u,&v);
57         add_edge(u,v);
58         add_edge(v,u);
59         ++ind[u];++ind[v];
60     }
61     for(int i=1,u,v;i<=m;++i){
62         scanf("%d%d",&u,&v);
63         lim[u].push_back(v);
64         ++ind[v];
65         vis[u]=true;
66     }
67     for(int i=1;i<=n;++i)
68         if(ind[i]==1)
69             q.push(i);
70     rt=Solve();
71     dfs(rt);
72     for(int i=1;i<=n;++i)
73         printf("%d\n",f[i]?1:0);
74     return 0;
75 }

 

上一篇:USACO 2019 January Contest Platinum: T1


下一篇:USACO 2019 January Contest Platinum T1: Redistricting