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

标签 负环 下的文章

October 31, 2019

洛谷P1768 天路

题意最优比率环数据范围:$1 \le n \le 7000,1 \le m \le 20000$题解$0/1$分数规划要求$$ans=\frac{\sum_i^{i \in E} v_i}{\sum_i^{i \in E} p_i}$$二分这个答案$mid$,将每条边的边更改为$$mid \cdot p_i-v_i$$跑负环即可代码:#include<iostream> #in...
October 31, 2019

洛谷P2850/USACO06DEC 虫洞Wormholes

题意判负环数据范围:$1 \le n \le 500,1 \le m \le 2500$题解$\text{dfs SPFA}$判负环即可代码:#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=510; const int M=5210...