[LOJ521]「LibreOJ β Round #3」绯色 IOI(抵达)
2021/7/29 23:08:08
本文主要是介绍[LOJ521]「LibreOJ β Round #3」绯色 IOI(抵达),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
壹、题目描述 ¶
传送门 to LOJ.
贰、题解 ¶
我们试图构造一些小的方案,发现一个特性:
- 合法方案,总是两个点互相为对方的避难节点;
这个结论并不难证明,由于最后是一棵树,故而没有环,而若不是相互避难,总有一个点找不到避难节点。
所以,对于是否有解,我们可以简单地判断一下,这个树是否存在匹配,否则,由于树的完美匹配是唯一的,我们只需要构造出字典序最小的复合限制条件的情况即可。
我们可以使用简单的建图方法,若要求 \(a_u<a_v\),那么连一条 \((u, v)\) 的有向边,最后使用类似拓扑的方法编号即可。
时间复杂度 \(\mathcal O(n\log n)\).
叁、参考代码 ¶
#include<cstdio> #include<algorithm> #include<vector> #include<cstdlib> #include<cstring> #include<queue> using namespace std; #define NDEBUG #include<cassert> namespace Elaina{ #define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i) #define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i) #define fi first #define se second #define mp(a, b) make_pair(a, b) #define Endl putchar('\n') #define mmset(a, b) memset(a, b, sizeof a) // #define int long long typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<class T>inline T fab(T x){ return x<0? -x: x; } template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); } template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); } template<class T>inline T readin(T x){ x=0; int f=0; char c; while((c=getchar())<'0' || '9'<c) if(c=='-') f=1; for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48)); return f? -x: x; } template<class T>inline void writc(T x, char s='\n'){ static int fwri_sta[1005], fwri_ed=0; if(x<0) putchar('-'), x=-x; do fwri_sta[++fwri_ed]=x%10, x/=10; while(x); while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed); putchar(s); } } using namespace Elaina; const int maxn=5e5; vector<int>g[maxn+5]; int n; inline void add_edge(int u, int v){ g[u].push_back(v), g[v].push_back(u); } inline void input(){ n=readin(1); int u, v; for(int i=1; i<n; ++i){ u=readin(1), v=readin(1); add_edge(u, v); } } int match[maxn+5]; void dfs(int u, int par){ for(int v: g[u]) if(v!=par) dfs(v, u); if(!match[u]){ if(par==0 || match[par]){ writc(-1); exit(0); } match[u]=par, match[par]=u; } } vector<int>lim[maxn+5]; int d[maxn+5]; inline void add_cons(int u, int v){ lim[u].push_back(v); ++d[v]; } inline void getconstraint(){ for(int u=1; u<=n; ++u){ for(int v: g[match[u]]) if(v!=u) add_cons(u, v); } } int a[maxn+5]; priority_queue< int, vector<int>, greater<int> >Q; inline void Topu(){ for(int i=1; i<=n; ++i) if(!d[i]) Q.push(i); int cur=0; while(!Q.empty()){ int u=Q.top(); Q.pop(); a[++cur]=u; for(int v: lim[u]) if(!--d[v]) Q.push(v); } } signed main(){ input(); dfs(1, 0); getconstraint(); Topu(); for(int i=1; i<=n; ++i) printf("%d ", a[i]); Endl; return 0; }
这篇关于[LOJ521]「LibreOJ β Round #3」绯色 IOI(抵达)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-20RabbitMQ教程:新手入门指南
- 2024-11-20Redis教程:新手入门指南
- 2024-11-20SaToken教程:新手入门指南
- 2024-11-20SpringBoot教程:从入门到实践
- 2024-11-20Java全栈教程:从入门到实战
- 2024-11-20Java微服务系统教程:入门与实践指南
- 2024-11-20Less教程:初学者快速上手指南
- 2024-11-20MyBatis教程:新手快速入门指南
- 2024-11-20QLExpress教程:初学者快速入门指南
- 2024-11-20订单系统教程:从入门到实践的全面指南