主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：CF1144F Graph Without Long Directed Paths
最后更新于 2025-08-28 09:02:12
作者
2huk
分类
题解
题解
CF1144F
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
注意到图中没有距离 $\ge 2$ 的路径等价于所有点的出度为 $0$ 或入度为 $0$。 我们令 $c_i = 0/1$ 表示 $i$ 的出度为 $0$ 还是入度为 $0$。 注意到相邻两点 $u, v$ 的 $c$ 一定不同。证明的话，如果这条边定向为 $u \to v$，那么 $c_u=1,c_v=0$。$u \gets v$ 同理。 因此变成了一个二分图染色的问题。
正在渲染内容...
点赞
0
收藏
0
