题目链接
观光奶牛
题目描述
给定一张 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 w，表示点 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
提示
【数据范围】
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\times \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\times 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\times w_i} pi−mid×wi时，是否存在正权环。
而判断是否存在正权环可以利用「SFPA」算法，基本思想与判断负环稍有不同。判断负环可以参考博主的另一篇文章：每周一算法：负环判断。判断正权环时：
- 要求最长路，即 d [ v ] < d [ u ] + w d[v] < d + w d[v]<d+w时，更新 v v v点到出发点的最长路；
- 当 v v v点到出发点的最长路被更新时，累加最长路中包罗的边数，即 c n t [ v ] = c n t [ u ] + 1 cnt[v]=cnt+1 cnt[v]=cnt+1
- 如果边数 c n t [ v ] > = n cnt[v]>=n cnt[v]>=n，说明图中存在正权环。
算法实现
综合上述，求 ∑ p i ∑ w i \frac{\sum p_i}{\sum w_i} ∑wi∑pi的最大值算法实现如下：
- 在 [ L , R ] [L,R] [L,R]范围内通过二分查找答案，对于中间结果 m i d mid mid：
- 利用SPFA算法判断当边权为 p i − m i d × w i p_i-mid\times w_i pi−mid×wi时，图中是否存在正权环
- 如果存在正权环，则在 [ m i d , R ] [mid,R] [mid,R]范围继续查找答案
- 否则不存在正权环，则在 [ L , m i d ] [L,mid] [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 <bits/stdc++.h>
- 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\n", L);
- return 0;
- }
|
