题目链接

观光奶牛

题目描述

给定一张

N

N

N 个点、

M

M

M 条边的有向图，每个点都有一个权值

p

i

p_i

pi​，每条边都有一个权值

w

i

w_i

wi​。

求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。

输出这个最大值。

注意：数据保证至少存在一个环。

输入格式

第一行包含两个整数

N

N

N 和

M

M

M。

接下来

N

N

N 行每行一个整数，表示

p

i

p_i

pi​。

再接下来

M

M

M 行，每行三个整数

a

a

a，

b

b

b，

w

[

i

]

w[i]

w[i]，表示点

a

a

a 和

b

b

b 之间存在一条边，边的权值为

w

i

w_i

wi​。

输出格式

输出一个数表示结果，保留两位小数。

样例 #1

样例输入 #1

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

样例输出 #1

6.00

提示

【数据范围】

2

≤

N

≤

1000

2≤N≤1000

2≤N≤1000,

2

≤

M

≤

5000

2≤M≤5000

2≤M≤5000,

1

≤

p

i

,

w

i

≤

1000

1≤p_i,w_i≤1000

1≤pi​,wi​≤1000

算法思想

根据题目描述，求的是图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大，不妨设即环上各点的权值之和为

∑

p

i

\sum p_i

∑pi​，各边的权值之和为

∑

w

i

\sum w_i

∑wi​，即求

∑

p

i

∑

w

i

\frac{\sum p_i}{\sum w_i}

∑wi​∑pi​​的最大值。这种解决“最优比率” 的问题，可以使用「01分数规划」。

01分数规划 ：01指取还是不取，分数即所求型式为

a

b

\frac{a}{b}

ba​，规划就是选取最好的方案。

01分数规划一般采用二分答案的方式求解。对于本题来说，即求是否存在

m

i

d

mid

mid，使环上各点的权值之和除以环上各边的权值之和大于

m

i

d

mid

mid，即

∑

p

i

∑

w

i

>

m

i

d

\frac{\sum p_i}{\sum w_i}>mid

∑wi​∑pi​​>mid，进一步整理可得：

∑

p

i

−

m

i

d

×

∑

w

i

>

0

\sum p_i-mid imes \sum w_i>0

∑pi​−mid×∑wi​>0

其中，

p

i

p_i

pi​表示节点

i

i

i的权值，为了方便处理，可以将节点的边权累加到该节点的出边上，那么不等式可以进一步转变为：

∑

(

p

i

−

m

i

d

×

w

i

)

>

0

\sum ({p_i-mid imes w_i})>0

∑(pi​−mid×wi​)>0

那么，要判断在包含环的图中是否存在

m

i

d

mid

mid，使环上各点的权值之和除以环上各边的权值之和大于

m

i

d

mid

mid，就等价于判断当图中边权为

p

i

−

m

i

d

×

w

i

{p_i-mid imes w_i}

pi​−mid×wi​时，是否存在正权环。

而判断是否存在正权环可以使用「SFPA」算法，基本思想与判断负环稍有不同。判断负环可以参考博主的另一篇文章：每周一算法：负环判断。判断正权环时：

• 要求最长路，即$d[v]<d[u]+w$
• 当$v$
• 如果边数$cnt[v]>=n$

算法实现

综合上述，求

∑

p

i

∑

w

i

\frac{\sum p_i}{\sum w_i}

∑wi​∑pi​​的最大值算法实现如下：

• 在$[L,R]$
• 如果存在正权环，则在$[mid,R]$
• 否则不存在正权环，则在$[L,mid]$

时间复杂度

本题中的01分数规划在二分答案的过程中，需要用SPFA算法判断正权环，时间复杂度为

O

(

k

M

l

o

g

W

)

O(kMlogW)

O(kMlogW)，其中

k

k

k是常数，

M

M

M为边数，

W

W

W为边权之和。

代码实现

#include 
using namespace std;
const int N = 1005, M = 5005;
int h[N], e[M], w[M], ne[M], idx;
int n, m;
int p[N], q[N], cnt[N];
double d[N];
bool st[N];
void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
bool check(double mid) //spfa判断是否存在正权环
{
memset(d, 0, sizeof d); //求最长路，初始化为0
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 u = q[hh ++];
if(hh == N) hh = 0; //循环队列
st[u] = false;
for(int i = h[u]; ~ i; i = ne[i])
{
int v = e[i];
if(d[v] < d[u] + p[u] - mid * w[i])
{
d[v] = d[u] + p[u] - mid * w[i];
cnt[v] = cnt[u] + 1;
if(cnt[v] >= n) return true;
if(!st[v]) 
{
q[tt ++] = v, st[v] = true;
if(tt == N) tt = 0;
}
}
}
}
return false;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> p[i];
memset(h, -1, sizeof h);
while(m --)
{
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
", L);
return 0;
}