牛客多校2 - Link with Game Glitch（spfa求正环，套汇，二分答案）

https://ac.nowcoder.com/acm/contest/33187/D

题意
给定 n 种物品，一共 m 种转换方案。
每种转换方案给出四个数 $a,b,c,d$，可以将 $k\ast a$ 个 $b$ 物品 转换为 $k\ast c$ 个 $d$ 物品，$k$ 可以是任意正实数。
现在存在一种兑换策略能得到无穷多某个物品，所以将兑换策略修改为：将 $k\ast a$ 个 $b$ 物品 转换为 $w\ast k\ast c$ 个 $d$ 物品。
求满足的 $w$ 的最大值。

$2\le n\le 1000,2\le m\le 2000$
$1\le b_i,d_i\le n,b_i\ne d_i,1\le a_i,c_i\le 10^3$

思路
先来看一个简化版：P1931 套利
给定几种货币的兑换汇率： a x b 表示 1 单位 a 货币可以兑换 x 单位 b 货币。
问，是否能够套汇？例如 1 美元兑换一圈之后变回 1.05 美元。

将每一种货币看作一个点，两点之间连边，边权为汇率。
如果一个点乘以边权之后比另一端点权值大，那就走过去更新，判断是否存在正环。spfa 判正环。

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
map<string,int> mp;

const int N = 20010, mod = 1e9+7;
int T, n, m;
vector<pair<int, double> > e[N];
double dist[N];
bool f[N];
int cntt[N];

bool spfa()
{
	queue<int> que;
	for(int i=1;i<=n;i++) que.push(i), f[i] = 1, cntt[i] = 1;
	
	while(que.size())
	{
		int x = que.front(); que.pop();
		f[x] = 0;
		
		for(auto it : e[x])
		{
			int tx = it.fi; double bi = it.se;
			if(dist[x] * bi > dist[tx])
			{
				dist[tx] = dist[x] * bi;
				cntt[tx] = cntt[x] + 1;
				if(cntt[tx] > n) return 1;
				if(!f[tx]) f[tx] = 1, que.push(tx);
			}
		}
	}
	return 0;
}

signed main(){
	int cs = 0;
	while(cin >> n && n)
	{
		mp.clear();
		
		for(int i=1;i<=n;i++){
			string s; cin >> s;
			mp[s] = i;
		}
		for(int i=1;i<=n;i++) e[i].clear(), dist[i] = 1;
		
		cin >> m;
		for(int i=1;i<=m;i++)
		{
			string sx, sy; double bi;
			cin >> sx >> bi >> sy;
			e[mp[sx]].push_back({mp[sy], bi});
		}
		
		if(spfa()) printf("Case %lld: Yes\n", ++cs);
		else printf("Case %lld: No\n", ++cs);
	}
	
	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

然后回到这个题
当 w 确定的时候便可以跑一遍 spfa 判断是否存在正环。
然后发现，当 w 越大的时候越容易出现正环，存在一个临界值 x，当 w 大于 x 时存在正环，当 w 小于 x 时不存在。
所以就可以二分答案，找到临界值。

注意要开 long double

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define fi first
#define se second
#define endl '\n'
#define double long double
map<int,int> mp;

/**/

const int N = 2010, mod = 1e9+7;
int T, n, m;
vector<pair<int, double> > e[N];
int f[N], cnt[N];
double dist[N];

bool spfa(double mid)
{
	queue<int> que;
	for(int i=1;i<=n;i++) que.push(i), f[i] = 1, dist[i] = 1, cnt[i] = 0;
	
	while(que.size())
	{
		int x = que.front(); que.pop();
		f[x] = 0;
		
		for(auto it : e[x])
		{
			int tx = it.fi; double bi = it.se;
			if(dist[x] * mid * bi > dist[tx])
			{
				dist[tx] = dist[x] * mid * bi;
				cnt[tx] = cnt[x] + 1;
				if(cnt[tx] >= n) return 0;
				if(!f[tx]) f[tx] = 1, que.push(tx);
			}
		}
	}
	return 1;
}

bool check(double mid){
	return spfa(mid);
}

signed main(){
	Ios;
	cin >> n >> m;
	for(int i=1;i<=m;i++)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		e[b].push_back({d, c*1.0/a});
	}
	
	double l = 0, r = 1;
	for(int i=1;i<=30;i++)
	{
		double mid = (l+r)/2;
		if(check(mid)) l = mid;
		else r = mid;
	}
	printf("%.10Lf\n", l);
	
	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

或者用 log 将乘法转化为 加法，减少实数大小：
dist[x] * mid * bi > dist[tx] 左右两边同时取 log，变为 dist[x] + log(mid) + log(bi) > dist[tx]，变过之后的 dist[x] 中存的实际上是 log(dist[x])。
这样用 double 精度就没问题了。

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long
#define pb push_back
#define fi first
#define se second
#define endl '\n'

const int N = 2010, mod = 1e9+7;
int T, n, m;
vector<pair<int, double> > e[N];
int f[N], cnt[N];
double dist[N];

bool spfa(double mid)
{
	queue<int> que;
	for(int i=1;i<=n;i++) que.push(i), f[i] = 1, dist[i] = 1, cnt[i] = 0;
	
	while(que.size())
	{
		int x = que.front(); que.pop();
		f[x] = 0;
		
		for(auto it : e[x])
		{
			int tx = it.fi; double bi = it.se;
			if(dist[x] + log(mid) + bi > dist[tx])
			{
				dist[tx] = dist[x] + log(mid) + bi;
				cnt[tx] = cnt[x] + 1;
				if(cnt[tx] >= n) return 0;
				if(!f[tx]) f[tx] = 1, que.push(tx);
			}
		}
	}
	return 1;
}

bool check(double mid){
	return spfa(mid);
}

signed main(){
	Ios;
	cin >> n >> m;
	for(int i=1;i<=m;i++)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		e[b].push_back({d, log(c*1.0/a)});
	}
	
	double l = 0, r = 1;
	for(int i=1;i<=30;i++)
	{
		double mid = (l+r)/2;
		if(check(mid)) l = mid;
		else r = mid;
	}
	printf("%.10lf\n", l);
	
	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