前言
思路
M a x ∑ f i / ∑ t i Max \sum fi / \sum ti Max∑fi/∑ti
这种都可以用 01 01 01分数来求
- 先判断最大值 ( 1000 / 1 1000/1 1000/1)
- 之后我们就可以二分答案
(图中是否存在一个环 使得值大于 m i d mid mid 因此答案应该在右边 否则在左边 --> 满足二分性质)
因此问题又来了 :
如何判断 图中是否存在环 满足这个条件
把除号变乘
∑
f
i
−
M
i
d
∑
t
i
>
0
\sum fi - Mid \sum ti > 0
∑fi−Mid∑ti>0
然后我们可以把所有的点权放到边权上 :
∑
f
i
+
∑
t
i
=
∑
(
f
i
+
t
i
)
\sum fi + \sum ti = \sum(fi+ti)
∑fi+∑ti=∑(fi+ti) 显然
所以公式继续化简
∑
(
f
i
−
M
i
d
∗
t
i
)
>
0
\sum (fi -Mid*ti) > 0
∑(fi−Mid∗ti)>0
这样子 就等价于 图中是否存在 正环
code
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m;
struct node
{
int to,val;
};
int f[N];
vector<node> g[N];
double dist[N];
int st[N],cnt[N];
bool check(double mid)
{
memset(dist,0,sizeof st);
memset(st,0,sizeof st);
memset(cnt,0,sizeof cnt);
queue<int> q;
for(int i=1;i<=n;i++)
{
q.push(i);
st[i] = 1;
}
while(!q.empty())
{
//<<"error"<<endl;
int t = q.front();
q.pop();
st[t] = 0;
for(auto x : g[t])
{
int j = x.to;
int w = x.val;
if(dist[j] < dist[t] + f[t] - mid * w)
{
dist[j] = dist[t] + f[t] - mid* w;
cnt[j] = cnt[t]+1;
if(cnt[j] >= n )
return true;
// 如果存在负环
if(!st[j])
{
q.push(j);
st[j] = 1;
}
}
}
}
return false;
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>f[i];
while(m -- )
{
int a,b,c;
cin>>a>>b>>c;
g[a].push_back({b,c});
}
double l= 0 ,r = 1010;
while(r - l > 1e-4) ///保留两位小数 1e-4 保留3位 1e-5
{
double mid =(l+r) /2;
if(check(mid))
l = mid;
else
r = mid;
}
printf("%.2lf",r);
}
int main()
{
solve();
return 0;
}