观光奶牛 详细题解
#T3 #SPFA判断正/负环 #二分查找
为啥现在突然发出来：翻自个笔记发现这篇写的挺好hhh
给定一张 \(L\) 个点、\(P\) 条边的有向图，每个点都有一个权值 \(f[i]\)，每条边都有一个权值 \(t[i]\)。
求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。
输出这个最大值。
注意：数据保证至少存在一个环。
输入格式
第一行包含两个整数 \(L\) 和 \(P\)。
接下来 \(L\) 行每行一个整数，表示 \(f[i]\)。
再接下来 \(P\) 行，每行三个整数 \(a，b，t[i]\)，表示点 \(a\) 和 \(b\) 之间存在一条边，边的权值为 \(t[i]\)。
输出格式
输出一个数表示结果，保留两位小数。
数据范围
\(2 \le L \le 1000\),
\(2 \le P \le 5000\),
\(1 \le f[i],t[i] \le 1000\)
输入样例：
5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2
输出样例：
6.00
思路
求有向图的一个环, 使“环上各点的权值之和”除以“环上各边的权值之和”最大。输出最大值。即 \(\frac{\sum f[i]}{\sum t[i]}\)最大。
这种类似的问题就是01分数规划问题, 有模板解法。其结果是存在上下界的, 最小因为权值都是正整数, 故为\(0\)（开区间）, 最大值则是分母为\(L\), 分子最大\(1000*L\) , 故最大值为\(1000\)。
而其两段性是很显然的, 设任取中间一个值\(mid\) , 判断能否找到一个环的\(\frac{\sum f[i]}{\sum t[i]}\)值大于\(mid\), 如果不能, 说明图中最大值小于\(mid\), 继续在 \((0,mid]\) 中搜索。若搜得到, 就说明图中最大值存在与\((mid, 1000L]\) 之间, 继续缩小范围。最终会找到满足条件的最大值。
判断是否存在一个环满足\(\frac{\sum f[i]}{\sum t[i]}>mid\) 先做一个数学上的变换：
\(\sum f[i] - \sum t[i]*mid > 0\)
把求和符号提出可得等价式子：\(\sum \{f[i] - t[i]*mid\}>0\)
当我们把这求和里面那块看做从其他点到\(i\)点的边, 那么这个式子的含义就是, 存在一个环, 它的边权和大于0。既然小于0的叫做负环, 那大于0就叫做正环。
求正环的操作跟负环类似, 只需要把求最小值换成求最大值即可。
求正负环还有个优化操作, 当寻找到一定次数之后可以提前结束以避免超时, 即定义一个变量\(count\) 记录当前搜索次数, 超过一般 \(2n/3n\)时就提前返回。
也可以把队列改成栈, 这样搜索模式为深度优先, 会更多的去更新刚入栈的点, 让\(cnt\)数组累加的更快。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e3 + 10, M = 1e5 + 10;
int n,m;
int h[N], e[M], w[M], ne[M], idx;
int f[N];
int q[N], cnt[N];
double dist[N];
bool st[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(st, 0, sizeof st);
memset(cnt, 0, sizeof cnt);
int hh = 0, tt = 0;
for(int i = 1; i <= n; i++)
q[tt++] = i, st[i] = true;
while(hh != tt)
{
int t = q[--tt];
st[t] = false;
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j] < dist[t] - w[i]*mid + f[j])
{
dist[j] = dist[t] - w[i]*mid + f[j];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return true;
if(!st[j])
q[tt++] = j, st[j] = true;
}
}
}
return false;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> f[i];
while(m--)
{
int a, b , c;
cin >> a >> b >> c;
add(a,b,c);
}
double l = 1, r = 1000;
while(r - l > 1e-4)
{
double mid = (l + r) / 2.0;
if(check(mid)) l = mid;
else r = mid;
}
printf("%.2lf", l);
return 0;
}