[Acwing] 361. 观光奶牛 01规划+spfa判断负环+二分

前言

传送门 :

思路

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 
using namespace std;

const int N = 1010;

int n,m;
struct node
{
    int to,val;
};
int f[N];
vector 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 q;
    
    for(int i=1;if[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;
}