题意有 $n(\le 1000)$ 个人，每个人有分数 $s[i]$ 。有 $S$ 组限制 $(A,B)$ ，要求 $s[A] > s[B]\times k$ 或 $s[A] > s[B]\times \frac{1}{k}$ ，如果不满足则 $A$ 需要女装。已知 $t$ 个人的初始分数。求最大的 $T$ ，使得限制变为 $s[A] > s[B]\times (k-T)$...
题意给出一个有向图，有边权 $w_i$ 和点权 $s_i$ 。要求找一个环，使 $\dfrac{\sum s_i}{\sum w_i}$ 最大。其中点数 $N\le 1000$ ，边数 $M\le 5000$ 。题解$0/1$ 分数规划。设当前二分值为 $mid$ ，题目即为$$\dfrac{\sum s_i}{\sum w_i} > mid$$$$\sum (s_i-mid\time...
题意给一个有向图，如果有负权回路输出-1，否则输出从起点 $S$ 到各个点的最短路长度，如果不连通输出NoPath。其中点数 $N\le 1000$ ，边数 $M\le 100000$ 。题解做法很显然，就是判负环+最短路。最开始我用的深搜 $spfa$ 判负环，求最短路就顺便继续用，然后就很开心的被卡超时了。正解就是用广搜 $spfa$ ，但我又不想删判负环的所以就写了两个。#includ...
题意定义圈的平均值为一个环上所有边的权值和 $\div$ 边的个数。给出一个有向图，求最小圈的平均值，保留 $8$ 位小数。其中点数 $n\le 3000$ ，边数 $m\le 10000$ 。题解$0/1$ 分数规划，直接二分答案 $mid$ ，然后对每条边减去 $mid$ 再跑 $spfa$ 判负环。如果有负环就缩小上界，否则增大下界。#include<bits/stdc++.h&...