求一道题
  • 板块灌水区
  • 楼主六楼溜刘
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/11/28 20:27
  • 上次更新2023/11/28 20:30:25
查看原帖
求一道题
537230
六楼溜刘楼主2023/11/28 20:27

题意大概是给你一张无向图,再给你若干个点对 (si,ti)(s_i,t_i),问存不存在给边定向的方案使得对于所有 (si,ti)(s_i,t_i) 均存在至少一条路径能从 sis_i 出发到达 tit_i。

做法大概是缩边双之后变成树的问题(一个边双显然能定向成强连通吧),然后树上差分解决。

我记得之前在哪里见过,但是找不到题了,BDFS 无果,前来求助万能的谷民。

2023/11/28 20:27
加载中...