竞赛图缩点后成链状（拓扑序唯一）
竞赛图缩点后成链状（拓扑序唯一）
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132993089
一个常见结论
竞赛图缩点后必然成链状。
不是真正的链，只是类似链的偏序关系。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-18
拆贡献算总和（抓住双射）+竞赛图与连通分量相关计数：arc163_d
拆贡献算总和（抓住双射）+竞赛图与连通分量相关计数：arc163_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132994501 https://atcoder.jp/contests/arc163/tasks/arc163_d 首先竞赛图有个性质： 然后有了这个性质，我们就可以考虑计数题的经典套路，拆贡献算总和。 考虑假如我们成功划分成两个集合 A,BA,BA,B ，其中一个可以为空（我们可以令 AAA 可以为空，防止算重），我们就记为算到一个新的...
2023-11-06
上下界网络流小结
上下界网络流小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132093889 正式请看：https://oi-wiki.org/graph/flow/bound/ 无源汇上下界可行流 新建源汇 S,TS,TS,T ，若 a→ba\to ba→b 有 [c,d][c,d][c,d] 。网络流中上界肯定满足。 我们变成： S→b,cS\to b,cS→b,c a→T,ca\to T,ca→T,c a→b,c−da\to b,c-da→b,c−...
2026-07-25
推性质转为2-sat问题：26暑杭电2-01
推性质转为2-sat问题：26暑杭电2-01 1001 xyz 问题 我们发现这个op有3个选择，是个3-sat问题，非常麻烦。 我们分析一下性质： 发现： 在 y=1,z=0y=1,z=0y=1,z=0 时，op只能是 ^ 和 & 否则，op选 | 一定比 ^ 更优，所以op只能是 | 和 & 现在op必然是二选一了 然后我们就暴力枚举4种情况： 如果 x=i,op=jx=i,op=jx=i,op=j 不成立，则： x=1−ix=1-ix=1−i 和 op=1−jop=1-jop=1−j 至少一个成立 就转化为2-sat问题了。 1234567891011...
2021-12-21
【USACO2021 Connecting Two Barns 】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15716522.html 题目 Farmer John’s farm consists of a set of NNN fields (1≤N≤105)(1 \leq N \leq 10^5)(1≤N≤105), conveniently numbered 1…N1 \ldots N1…N. Between these fields are MMM bi-directed paths (0≤M≤105)(0 \leq M \leq 10^5)(...
2021-12-02
【[ARC063C] Integers on a Tree】
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15633812.html 题目链接 对于最小的点，与它相连的没填的点中，都赋值为这个点点权+1。 这样子贪心就算旁边的点必然会比这个点大，所以+1是没错的。 最后再遍历所有边检验答案合法性。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666...
2023-08-03
网络最大流
网络最大流 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132091032 < Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流 - 洛谷 > 先bfs分层 2.dfs增广，当前弧优化 重复以上步骤 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545...