【洛谷5157】[USACO18DEC] The Cow Gathering P(拓扑)

2021年09月15日 阅读数:3
这篇文章主要向大家介绍【洛谷5157】[USACO18DEC] The Cow Gathering P(拓扑),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
给定一棵$n$个点的树,每次能够选择删除一个叶节点。有$m$个限制$(x,y)$,表示$x$必须先于$y$被删除。要求判断每一个点是否可能成为最后剩下的点。

点此看题面c++

  • 给定一棵\(n\)个点的树,每次能够选择删除一个叶节点。
  • \(m\)个限制\((x,y)\),表示\(x\)必须先于\(y\)被删除。
  • 要求判断每一个点是否可能成为最后剩下的点。
  • \(n,m\le10^5\)

拓扑求一个可行解

其实就一个很简单的贪心想法,咱们每次选择一个不受限制的叶节点删去。ide

也就是说,要求剩余度数\(\le1\)且剩余受限制数\(=0\),直接拓扑排序便可。spa

若是找不到这样一个可行解,就说明无解了。code

从一解到全解

以求出来的这一个可行解为根。排序

考虑一个限制\((x,y)\),至关于以\(y\)为根时的\(x\)子树内全部点都不可能成为最后剩下的点。get

因为当前以一个可行解为根,\(y\)必定不在\(x\)子树内,故以\(y\)为根时的\(x\)子树就是当前的\(x\)子树。it

直接给\(x\)打个标记,而后从\(rt\)出发\(dfs\)一遍,不访问任何有标记的点,则被访问到的点就是答案。class

代码:\(O(n)\)

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
using namespace std;
int n,m,deg[N+5],cnt[N+5],p[N+5],ans[N+5],ee,lnk[N+5];struct edge {int to,nxt;}e[2*N+5];vector<int> G[N+5];
int q[N+5];I int Topo()//拓扑求一个可行解
{
	RI i,k,H=1,T=0;vector<int>::iterator it;for(i=1;i<=n;++i) deg[i]==1&&!cnt[i]&&(q[++T]=i);W(H<=T)
	{
		for(i=lnk[k=q[H++]];i;i=e[i].nxt) --deg[e[i].to]==1&&!cnt[e[i].to]&&(q[++T]=e[i].to);//更新度数
		for(it=G[k].begin();it!=G[k].end();++it) !--cnt[*it]&&deg[*it]<=1&&(q[++T]=*it);//更新受限制数
	}return T^n?-1:q[T];//无解返回-1,不然返回拓扑排序中最后一个点
}
I void dfs(CI x,CI lst=0) {ans[x]=1;for(RI i=lnk[x];i;i=e[i].nxt) e[i].to^lst&&!p[e[i].to]&&(dfs(e[i].to,x),0);}//遍历,不访问任何有标记的点
int main()
{
	RI i,x,y;for(scanf("%d%d",&n,&m),i=1;i^n;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x),++deg[x],++deg[y];
	for(i=1;i<=m;++i) scanf("%d%d",&x,&y),++cnt[y],G[x].push_back(y);
	RI rt=Topo();if(~rt) {for(i=1;i<=n;++i) !G[i].empty()&&(p[i]=1);dfs(rt);}//给有限制的点打上标记
	for(i=1;i<=n;++i) putchar(48|ans[i]),putchar('\n');return 0;
}
败得义无反顾,弱得一无可取