Link with Game Glitch

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

Problem

给出n种物品,These items can be converted.给出m条转换规则,形如：$a$ 个 $b$ 物品 可以转换为 $c\times w$ 个 $d$ 物品.问：$w$ How much to take,In order to prevent these items from being converted into an infinite number of items.

Solution

It's obviously a graph theory question.边: $c\to d$, 边权: $\frac{cw}{a}$

1. To make it impossible to convert into an infinite number of items,Then it is necessary to determine whether such one exists“环”.
   假设：The edge weights on this ring are $e_i$, 环上有 $k$ 个节点
   那么,当满足 $e_1\times e_2\times ...\times e_k>1$ 时, can be converted into an infinite number of items
2. 考虑到精度问题,Logarithms can be taken left and right
   $$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}$$
   到此为止,The title has been converted to side weights $-log(\frac{wc}{a})$ the negative loop problem
3. 最后注意：The figure may be “森林“结构.

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];
//vMarks whether the point is in the queue
//visMarks whether the point has been traveled,Used to traverse the forest structure
//cntThe number of updates to mark the point,更新次数 >= 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;//find the negative ring

					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;
}