Link with Game Glitch（spfa判负环）

"蔚来杯"2022牛客暑期多校训练营2

Problem

给出n种物品，这些物品可以进行转换。给出m条转换规则，形如：$a$ 个 $b$ 物品 可以转换为 $c\times w$ 个 $d$ 物品。问：$w$ 最大取多少，才能使这些物品无法转换成无限多的物品。

Solution

明显就是一道图论题目。边: $c\to d$, 边权: $\frac{cw}{a}$

1. 若要使无法转换成无限多的物品，那么就需要判断是否存在这样的一个“环”。
   假设：这个环上的边权为 $e_i$， 环上有 $k$ 个节点
   那么，当满足 $e_1\times e_2\times ...\times e_k>1$ 时， 则可以转换成无限多的物品
2. 考虑到精度问题，可以左右取对数
   $$log(e_1\times e_2\times ...\times e_k)>log(1)=0$$
   即：$$\begin{gathered} log(e_1)+log(e_2)+...+log(e_k)>0 \\ -log(e_1)-log(e_2)-...-log(e_k)<0 \end{gathered}$$
   到此为止，题目已经转换成边权为 $-log(\frac{wc}{a})$ 的判负环问题
3. 最后注意：该图可能为 “森林“结构。

Code

const int N = 4e3 + 3;

int n, m;

int h[N], net[N], e[N], a[N], c[N], tot;
void add(int x, int y, int z, int zz)
{
	e[++tot] = y;
	a[tot] = z; c[tot] = zz;
	net[tot] = h[x];
	h[x] = tot;
}


double d[N];
int v[N], vis[N], cnt[N];
//v标记该点是否在队列中
//vis标记该点是否已经走过，用来遍历森林结构
//cnt标记该点的跟新次数，更新次数 >= n 则存在负环
bool spfa(double w)
{
	for (int i = 1; i <= n; i++)
		d[i] = 1e18, v[i] = 0, vis[i] = 0;
	
	for (int i = 1; i <= n; i++)
	{
		if (vis[i]) continue;
		vis[i] = 1;
		
		queue<int> q;
		q.push(i);
		d[i] = 0; v[i] = 1;
		cnt[i] = 0;
		while (sz(q))
		{
			int x = q.front(); q.pop();
			v[x] = 0; 
			for (int i = h[x]; i; i = net[i])
			{
				int y = e[i]; double z = -log(w * c[i] / a[i]);
				if (d[y] > d[x] + z)
				{
					vis[x] = 1;//标记走过的点
					
					cnt[y] = cnt[x] + 1;
					if (cnt[y] >= n) return 0;//发现负环

					d[y] = d[x] + z;
					if (v[y] == 0) q.push(y), v[y] = 1;
				}
			}
		}
	}

	return 1;
}

int main()
{
	IOS;
	cin >> n >> m;
	for (int i = 1, a, b, c, d; i <= m; i++)
	{
		cin >> a >> b >> c >> d;
		add(b, d, a, c);
	}

	double l = 0, r = 1;
	while (r - l > esp)
	{
		double mid = (l + r) / 2;
		if (spfa(mid)) l = mid;
		else r = mid;
	}

	cout << fixed << setprecision(10) << r << endl;


	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80