夢に僕らで帆を張って
来るべき日のために夜を超え

标签 强连通分量 下的文章

October 27, 2019

洛谷P3119/USACO15JAN 草鉴定Grass Cownoisseur

题意给出一张有向图,可以逆行$1$次,求从$1$回到$1$最多经过几个点数据范围:$1 \le n,m \le 100000$题解首先$\mathrm{Tarjan}$缩点,并将新点点权赋为所在强连通分量的点数新图建分层图,连接两层之间为反向边,意为逆行$1$次从$1$所在的强连通分量开始跑$\mathrm{SPFA}$最长路,答案即为到第二层中$1$所在的强连通分量对应的点的距离代码:#i...
October 27, 2019

洛谷P2002 消息扩散

题意$n$个城市,$m$条关系表示消息传输关系,求至少需要在几个城市发布消息才能让这所有$n$个城市都得到消息数据范围:$n \le 100000,m \le 500000$题解$\mathrm{Tarjan}$缩点后统计入度为$0$的点即可代码:#include<iostream> #include<cstdio> #include<stack> usi...
October 25, 2019

洛谷P2515/HAOI2010 软件安装

题意有$n$个软件可以安装,每个软件会占$w_i$的磁盘空间,价值为$v_i$ ,每个软件都有至多一个依赖。剩余磁盘空间为$m$,求安装软件的价值最大值数据范围:$0 \le n \le 100,0 \le m \le 500,0 \le v_i \le 1000$题解因为可能存在环,即必须全部安装才能有贡献,所以用$\mathrm{Tarjan}$缩点之后便是树形$\mathrm{dp}$...
October 24, 2019

洛谷P1407/国家集训队 稳定婚姻

题意略数据范围:$1 \le n \le 4000,0 \le m \le 20000$题解若成环,则一定是男$\rightarrow$女$\rightarrow$男$\rightarrow \dots$交替,所以建边时两种建边方向应相反,即夫妻关系由男$\rightarrow$女,情侣关系由女$\rightarrow$男然后跑$\mathrm{Tarjan}$即可代码:#include&l...