01规划
设答案为 $ans$。
二分答案,设当前二分值为 $mid$。
设一个环 $S$ 的边权为 $t_1, t_2, t_3…$,点权为 $f_1, f_2, f_3…$
-
若 $mid <= ans$,即存在一个环$S$使得 $mid <= \frac{\sum f_i}{\sum t_i}$,变换一下:$\sum(mid * t_i - f_i) <= 0$
-
否则,则 $mid > ans$
每次 $check$ 的时候,一条 $u$ 指向 $v$,边权为 $w$ 的边权变为:
$w * mid - f_u$。我们只需检查这个图是否存在负环即可。
时间复杂度
最坏情况存在长度为 $L$ 的环, $\sum t_i = L, \sum f_i = 1000L$。故答案最大可能是 $1000$。
$Log_210^7 \approx 24$
$O(24*LP)$。判负环的时间一般情况下低于 $O(LP)$。
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1005, M = 5005;
int n, q[N * M], m, f[N], cnt[N];
int head[N], numE = 0;
double dis[N];
bool vis[N];
struct E{
int next, v, w;
}e[M];
void add(int u, int v, int w) {
e[++numE] = (E) { head[u], v, w };
head[u] = numE;
}
bool inline check(double mid) {
int hh = 0, tt = -1;
for (int i = 1; i <= n; i++)
vis[i] = true, dis[i] = cnt[i] = 0, q[++tt] = i;
while(hh <= tt) {
int u = q[hh++];
vis[u] = false;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
double w = e[i].w * mid - f[u];
if(dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if(cnt[v] >= n) return true;
if(!vis[v]) q[++tt] = v;
}
}
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", f + i);
for (int i = 1, u, v, w; i <= m; i++) {
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
}
double l = 0, r = 1000, eps = 1e-4;
while(r - l > eps) {
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
printf("%.2lf\n", r);
return 0;
}
常数二分复杂度应该还要大很多吧?直接取log是不是有一些不妥?
emm也许是的,因为这是实数二分,我们设的 eps 是 1e-4,相当于对 $1000 * 10^4 = 10^7$ 值域二分, 复杂度应该是对这个取log,差不多是 24 左右,不会大太多。。已经修正
嗯嗯😁
请问为什么您这种写法后面不用st[v] = 1
y总那个去掉了就错了
%%%%%%%%%
真是妙蛙种子妙妙屋,妙到家了
求问: ∑(mid∗ti−fi)<=0 这里不是含有0环吗
他的代码里面没有0环
%%%%%
我没有用结构体,直接用的链式存储,把代码改写了一下就超时了,大佬知道为什么吗?
点数是
1010
,边数是5010
对于这个题来说你的spfa应该要求最长路
y总写的是最长路, 墨佬把公式取反了,所以还是求的最短路,我觉得更容易懂(虽然改成最长路只是改变了大于号)
请问下,为什么
一开始要全入队,而且可以dis[i]=0 而不是INF, dis[1]=0呢?
负环的原理就是说存在一个长度为n的最短路路径,这样无限走肯定有个负环。那么其实跑的是一个多源的最短路,要检查每个点出发能否无限走最短路,所以这里dis具体是多少没有多大意义,只是为了表达相对大小关系,如果存在负环,即可以一直更新一直走~
emm~有道理hh
有一说一,我把$dis(1):=0,dis(x):=\infty (x\ne 1)$,然后队列只push1进去也是可以的
如果图不联通还可以吗?
哦是不太行,这题侥幸过了(判负环大多用在差分约束,差分约束一般都连通,所以居然没发现我一直写的没法处理非连通图)Orz