第一种 AC

以不女装为条件。

$$log(a_i) \ge log(B_i)+log(k_i-t) \\ log(a_i) \gt log(B_i) - log(k_i+t)$$

如果有环，说明有女装；

否则，无女装。

跑最长路。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
inline void read(int& x){
    bool f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=!f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=(f?x:-x);return;
}
const double eps = 1e-6;
const int N = 1005;
const int Inf = 0x3f3f3f3f;
struct Edge {
	int to, next, flag;
	double w;
} e[N * 3];
int n, s, t, len, head[N], cnt[N];double dis[N];
bool vis[N];
double maxn = 10;
void Insert(const int& u, const int& v, const double& w, const int& flag) {
	e[++len] = Edge{v, head[u], flag, w};
	head[u] = len;
}
void Read() {
	read(n);read(s);read(t);
	for (int i = 1, o, a, b, k; i <= s; ++i) {
		read(o);read(a);read(b);read(k);
		if (o == 1) {
			Insert(b, a, (double)k, 1);
			//保证e[i].w - T为正数,实数精度不管
			maxn = min(maxn, (double)k);
		}
		if (o == 2) {
			Insert(b, a, k, 2);
		}
	}
	for (int i = 1, c, x; i <= t; ++i) {//超级节点
		read(c);read(x);
		Insert(n + 1, c, log(x), 3);
		Insert(c, n + 1, -log(x), 3);
	}
}
bool SPFA(const double& T) {
	queue<int> q;
	for (int i = 1; i <= n + 1; ++i)
		vis[i] = true, q.push(i), cnt[i] = dis[i] = 0;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		vis[now] = false;
		for (int i = head[now], v; i; i = e[i].next) {
			v = e[i].to;
			double w;
			switch (e[i].flag) {
				case 1:
					w = log(e[i].w - T);
					break;
				case 2:
					w = -log(e[i].w + T);
					break;
				case 3:
					w = e[i].w;
					break;
			}
			if (dis[v] < dis[now] + w) {
				dis[v] = dis[now] + w;
				cnt[v] = cnt[now] + 1;
				if (cnt[v] == n + 1)
					return false;
				if (!vis[v]) vis[v] = true, q.push(v);
			}
		}
	}
	return true;
}
void EF(double l, double r) {
	double mid;
	while (r - l > eps) {
		mid = l + (r - l) / 2;
		if (SPFA(mid)) r = mid;
		else l = mid;
	}
	printf("%.6lf\n", l);
}
int main() {
	Read();
	if (SPFA(0)) {
		printf("-1\n");
		return 0;
	}
	EF(0, maxn);
	return 0;
}

第二种 WA

以要女装为条件。

$$log(a_i) \lt log(B_i)+log(k_i-t) \\ log(a_i) \le log(B_i) - log(k_i+t)$$

如果有环，说明无女装；

否则，有女装。

跑最短路

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
const double eps = 1e-6;
const int N = 1005;
const int Inf = 0x3f3f3f3f;
struct Edge {
	int to, next, flag;
	double w;
} e[N * 3];
int n, s, t, len, head[N], cnt[N];double dis[N];
bool vis[N];
double maxn = 10;
void Insert(const int& u, const int& v, const double& w, const int& flag) {
	e[++len] = Edge{v, head[u], flag, w};
	head[u] = len;
}
void Read() {
	scanf("%d%d%d", &n, &s, &t);
	for (int i = 1, o, a, b; i <= s; ++i) {
		double k;
		scanf("%d%d%d%lf", &o, &a, &b, &k);
		if (o == 1) {
			Insert(b, a, k, 1);
			//保证e[i].w - T为正数,实数精度不管
			maxn = min(maxn, k);
		}
		if (o == 2) {
			Insert(b, a, k, 2);
		}
	}
	for (int i = 1, c, x; i <= t; ++i) {//超级节点
		scanf("%d%d", &c, &x);
		Insert(n + 1, c, log(x), 3);
		Insert(c, n + 1, -log(x), 3);
	}
}
bool SPFA(const double& T) {
	queue<int> q;
	for (int i = 1; i <= n + 1; ++i)
		vis[i] = true, q.push(i), cnt[i] = dis[i] = 0;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		vis[now] = false;
		for (int i = head[now], v; i; i = e[i].next) {
			v = e[i].to;
			double w;
			switch (e[i].flag) {
				case 1:
					w = log(e[i].w - T);
					break;
				case 2:
					w = -log(e[i].w + T);
					break;
				case 3:
					w = e[i].w;
					break;
			}
			if (dis[v] > dis[now] + w) {
				dis[v] = dis[now] + w;
				cnt[v] = cnt[now] + 1;
				if (cnt[v] == n + 1)
					return true;
				if (!vis[v]) vis[v] = true, q.push(v);
			}
		}
	}
	return false;
}
void EF(double l, double r) {
	double mid;
	while (r - l > eps) {
		mid = l + (r - l) / 2;
		if (SPFA(mid)) r = mid;
		else l = mid;
	}
	printf("%.6lf\n", l);
}
int main() {
	Read();
	if (SPFA(0)) {
		printf("-1\n");
		return 0;
	}
	EF(0, maxn);
	return 0;
}

为什么不对呢？按道理可以的。