Solution - 倍杀测量者

其实是为了光明正大地 waste time。不然谁会写这种垃圾题解？

首先这个有一个非常明显的单调性，考虑直接二分答案。那么就转化为了判定类似于 \(A_i \geq k \times B_i\) 等条件是否成立。这个乘号看起来很突兀，于是用一个 trick，加上一个 \(\log\)，于是相当于 \(\log A_i \geq \log k + \log B_i\)。我去，直接差分约束。那么如果没有负环就代表没有人女装。

然后注意一下二分的边界，\(r = \min\limits_{i = 1} ^ n k_i (o_i = 1)\)。

namespace liuzimingc {
const int N = 1e3 + 5;
#define endl '\n'

int n, m, t, o[N], a[N], b[N], k[N], score[N], cnt[N];
double dis[N];
vector<pair<int, double>> e[N];
queue<int> q;
bool vis[N];

bool check(double mid) {
	for (int i = 0; i <= n + 1; i++) e[i].clear();
	for (int i = 1; i <= m; i++)
		if (o[i] == 1) e[a[i]].push_back(make_pair(b[i], -log(k[i] - mid)));
		else e[a[i]].push_back(make_pair(b[i], log(k[i] + mid)));
	for (int i = 0; i <= n; i++) {
		if (score[i]) {
			e[i].push_back(make_pair(0, -log(score[i])));
			e[0].push_back(make_pair(i, log(score[i])));
		}
		e[n + 1].push_back(make_pair(i, 0));
	}
	while (q.size()) q.pop();
	for (int i = 0; i <= n + 1; i++) vis[i] = false, cnt[i] = 0, dis[i] = 1e18;
	q.push(n + 1);
	vis[n + 1] = true;
	dis[n + 1] = 0;
	while (q.size()) {
		int u = q.front(); q.pop();
		vis[u] = false;
		for (const auto &i : e[u]) {
			int v = i.first;
			double w = i.second;
			if (dis[u] + w < dis[v]) {
				dis[v] = dis[u] + w;
				cnt[v] = cnt[u] + 1;
				if (cnt[v] >= n + 2) return true;
				if (!vis[v]) q.push(v), vis[v] = true;
			}
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	double l = 0, r = 10;
	cin >> n >> m >> t;
	for (int i = 1; i <= m; i++) {
		cin >> o[i] >> a[i] >> b[i] >> k[i];
		if (o[i] == 1) r = min(r, (double)k[i]);
	}
	while (t--) {
		int stu;
		cin >> stu;
		cin >> score[stu];
	}
	if (!check(0)) return cout << -1 << endl, 0;
	while (r - l > 1e-6) {
		double mid = (l + r) / 2;
		if (check(mid)) l = mid;
		else r = mid;
	}
	cout << fixed << setprecision(10) << l << endl;
	return 0;
}
} // namespace liuzimingc