当前位置:网站首页>AcWing 361. 观光奶牛 题解(spfa求正环)
AcWing 361. 观光奶牛 题解(spfa求正环)
2022-07-06 18:00:00 【乔大先生】
AcWing 361. 观光奶牛
由图中公式可知,这道题让求的是有一个正环即可,所以要寻找的是最长路径,所以if中的判断句判断的是能否找到更长边值
#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]; //记录边数
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]){
//要求的是正环,所以是最长路
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; //这个值可以,可以试图找更大值
else r = mid; //这个值不行,要找更小值
}
printf("%.2lf\n", r);
return 0;
}
边栏推荐
- Failed to successfully launch or connect to a child MSBuild. exe process. Verify that the MSBuild. exe
- C语言实例_5
- Your cache folder contains root-owned files, due to a bug in npm ERR! previous versions of npm which
- Meet in the middle
- 【信号与系统】
- Google released a security update to fix 0 days that have been used in chrome
- 736. Lisp 语法解析 : DFS 模拟题
- c语言—数组
- 安利一波C2工具
- LLDP兼容CDP功能配置
猜你喜欢
HMM 笔记
[signal and system]
Send template message via wechat official account
让我们,从头到尾,通透网络I/O模型
2022 Google CTF segfault Labyrinth WP
字节P7专业级讲解:接口测试常用工具及测试方法,福利文
【案例分享】网络环路检测基本功能配置
JTAG debugging experience of arm bare board debugging
Yunna | work order management software, work order management software app
【C语言进阶篇】指针的8道笔试题
随机推荐
Your cache folder contains root-owned files, due to a bug in npm ERR! previous versions of npm which
字节P7专业级讲解:接口测试常用工具及测试方法,福利文
Transplant DAC chip mcp4725 to nuc980
Let's see through the network i/o model from beginning to end
LeetCode:1175. 质数排列
2022 Google CTF SEGFAULT LABYRINTH wp
移植DAC芯片MCP4725驱动到NUC980
ClickHouse字段分组聚合、按照任意时间段粒度查询SQL
THREE.AxesHelper is not a constructor
第三方跳转网站 出现 405 Method Not Allowed
DS-5/RVDS4.0变量初始化错误
HMM 笔记
数据手册中的词汇
c语言—数组
Vocabulary in Data Book
How to prevent overfitting in cross validation
How to manage distributed teams?
2022 Google CTF SEGFAULT LABYRINTH wp
NEON优化:矩阵转置的指令优化案例
Clickhouse fields are grouped and aggregated, and SQL is queried according to the granularity of any time period