(2022 Niuke multi school) D-Link with game glitch (SPFA)

subject ：

The sample input ：

3 3
1 1 2 2
1 2 2 1
1 3 1 1

Sample output ：

0.5000000000

The question ： Given m A way of synthesizing objects , Find a maximum synthetic loss parameter w, So that all items cannot be obtained infinitely through infinite synthesis .

analysis ： It should be noted that the greater the loss parameter value, the less the loss when the article is synthesized , So that is to say, this topic w Monotonicity , When w When reaching a boundary value ,w No matter how big, there will be some items that can be obtained indefinitely , and w No matter how small, all items can't be obtained indefinitely , So we can solve it directly by dichotomy .

For one w We judge whether it is feasible , Is equivalent to this topic ：Arbitrage（spfa）_AC__dream The blog of -CSDN Blog w

Only need to run once spfa Judge whether there is a positive ring in the figure below to know whether there is an item that can be synthesized infinitely , But there is another very important point of this topic that needs special attention , That is to say a,c The boundary of the scope is 1e3, All in all 1000 Items , In extreme cases 1 After exchanging items, you will get 1e3000, This number is relatively large , The loss of accuracy will be serious , So we can't directly update the original data , We can Take the logarithm of the original data and then update it . To put it a little bit ： If opened long double You can also put this topic ac, But I still hope you will pay attention to this skill .

W Is the loss parameter   a[i] individual t Items can be exchanged c[i] individual j goods , be

Update method of original data :

if(d[t]*c[i]/a[i]*W>=d[j])     d[j]=d[t]*c[i]/a[i]*W

Update method after taking logarithm ：

if(log(d[t])+log(c[i]/a[i])+log(W)>=log[d[j]])    log[d[j]=log(d[t])+log(c[i]/a[i])+log(W)

The basis of this transformation is log A function is monotonically increasing in its domain , So if d[t]*c[i]/a[i]*W>=d[j], Then there are log(d[t])+log(c[i]/a[i])+log(W)>=log[d[j]]. We directly order d[i]=log(d[i]), Then make w[i]=log(c[i]/a[i]),W=log(W) that will do , Then the update condition becomes ：

if(d[t]+w[i]+W>d[j]) d[j]=d[t]+w[i]+W

Then just use one cnt The array can determine the positive ring , Be careful spfa Judge the ring , It is possible that the graph is not connected , So we need to add all points to the queue at the beginning . See code for details ：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e4+10;
int h[N],e[N],ne[N],cnt[N],idx;
double w[N],d[N];
bool vis[N];
int n,m;
void add(int x,int y,double z)
{
	e[idx]=y;
	w[idx]=z;
	ne[idx]=h[x];
	h[x]=idx++;
}
bool spfa(double W)
{
	W=log(W);
	queue<int>q;
	for(int i=1;i<=n;i++)
	{
		cnt[i]=0;
		vis[i]=false;
		q.push(i);
	}
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		vis[t]=false;
		for(int i=h[t];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(d[t]+w[i]+W>d[j])
			{
				d[j]=d[t]+w[i]+W;
				cnt[j]=cnt[t]+1;
				if(cnt[j]>=n) return true;
				if(!vis[j])
				{
					q.push(j);
					vis[j]=true;
				}
			}
		}
	}
	return false;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) h[i]=-1;
	for(int i=1;i<=m;i++)
	{
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		add(b,d,log(1.0*c/a));
	}
	double l=0.0,r=1.0;
	while(r-l>1e-8)
	{
		double mid=(l+r)/2;
		if(spfa(mid)) r=mid;// If there is a positive ring, you need to increase the loss rate  
		else l=mid;
	}
	printf("%.7lf",l);
	return 0;
}