当前位置:网站首页>AcWing 361. Sightseeing cow problem solution (SPFA seeking positive ring)
AcWing 361. Sightseeing cow problem solution (SPFA seeking positive ring)
2022-07-07 01:37:00 【Mr. Qiao Da】
AcWing 361. Sightseeing cows
According to the formula in the figure , What this problem asks is to have a positive ring , So we are looking for the longest path , therefore if The judgement sentence in determines whether a longer boundary value can be found
#include<bits/stdc++.h>
using namespace std;
const int N = 1010, M = 5210;
int h[N], ne[M], e[M], w[M], idx;
int n, m;
double dist[N];
int wf[N];
bool st[N];
int cnt[N]; // Record edges
void add(int a, int b, int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx ++ ;
}
bool check(double mid){
memset(dist, 0, sizeof dist);
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] = true;
}
while(q.size()){
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; ~i; i = ne[i]){
int j = e[i];
if(dist[j] < dist[t] + wf[t] - mid * w[i]){
// What is required is a positive ring , So it's the longest way
dist[j] = dist[t] + wf[t] - mid * w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return true;
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main()
{
cin>>n>>m;
for(int i = 1; i <= n; i ++ ) cin>>wf[i];
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++ ){
int a, b, c;
cin>>a>>b>>c;
add(a, b, c);
}
double l = 0, r = 1e6;
while(r - l > 1e-4){
double mid = (l + r) / 2;
if(check(mid)) l = mid; // This value can , You can try to find a larger value
else r = mid; // This value is not good , Looking for a smaller value
}
printf("%.2lf\n", r);
return 0;
}
边栏推荐
猜你喜欢
百度飞将BMN时序动作定位框架 | 数据准备与训练指南 (上)
ClickHouse字段分组聚合、按照任意时间段粒度查询SQL
Make Jar, Not War
AcWing 361. 观光奶牛 题解(spfa求正环)
Go zero micro service practical series (IX. ultimate optimization of seckill performance)
第三方跳转网站 出现 405 Method Not Allowed
Make Jar, Not War
Transplant DAC chip mcp4725 to nuc980
[advanced C language] 8 written questions of pointer
Js逆向——捅了【马蜂窝】的ob混淆与加速乐
随机推荐
hdu 4661 Message Passing(木DP&amp;组合数学)
长按按钮执行函数
[chip scheme design] pulse oximeter
AI 从代码中自动生成注释文档
7.6 simulation summary
新工作感悟~辞旧迎新~
增加 pdf 标题浮窗
Table table setting fillet
dvajs的基础介绍及使用
Neon Optimization: summary of performance optimization experience
Right mouse button customization
736. LISP syntax parsing: DFS simulation questions
鼠标右键 自定义
【芯片方案设计】脉搏血氧仪
2022 Google CTF SEGFAULT LABYRINTH wp
AcWing 904. 虫洞 题解(spfa求负环)
【C语言进阶篇】指针的8道笔试题
POJ 3177 Redundant Paths POJ 3352 Road Construction(双连接)
一起看看matlab工具箱内部是如何实现BP神经网络的
Start from the bottom structure to learn the customization and testing of fpga---- FIFO IP