算法提高课-图论-负环-AcWing 1165. 单词环：spfa判正环、二分、01分数规划

文章目录

• • • 题目分析
    • 题目链接

题目分析

来源：acwing

分析：
如何建图？

这样建图。以样例举例。起点是前两个字母，终点是末尾两个字母，边权是字符串的长度。

我们求的是什么呢？

题目要求$\frac{\Sigma 边权}{\Sigma 1(点的个数)}$的最大值，这种问题称为01分数规划，通俗点说，就是一堆的和除以一堆的和，要求比值最大。

我们可以通过二分来做，二分啥呢？就是对于一个环，二分一个mid值，判断是否满足$\frac{\Sigma 边权}{\Sigma 1(点的个数)}\ge mid$，然后我们就可以来不断更改二分的区间，直到找到$\frac{\Sigma 边权}{\Sigma 1}$的最大值。

思路确定了，那么具体如何实现呢？

$\frac{\Sigma 边权}{\Sigma 1}\ge mid$ 由于这里的边都是正权边，所以可以移项，变成

$$\Sigma 边权-mid\times \Sigma 1\ge 0$$

将求和符号提出，亦等价于：

$$\Sigma (边权-mid)\ge 0$$
等价于 图中存在正环

下面就是默写spfa判正环。

当然建边的时候，需要把ab，ba这样的字母映射到一个整数（因为每一维都是26个英文字母的一个，这里用26 进制来做），是如下这样做的：

int left= (str[0] - 'a') * 26 + str[1] - 'a'; int right = (str[len -2 ] - 'a') * 26 + str[len - 1] - 'a';

ac代码

#include<bits/stdc++.h> using namespace std; const int N = 700, M = 100010; int n; int h[N], e[M], w[M], ne[M], idx; double dist[N]; int q[N], cnt[N]; bool st[N];void add(int a, int b, int c){e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; }bool check(double mid){memset(st, 0, sizeof st);memset(cnt, 0, sizeof cnt);int number = 26 * 26;queue<int> q;for(int i = 0; i < number ;i ++) q.push(i), st[i] = true;int count = 0; // 防止超时，做的优化while(q.size()){auto 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] + w[i] - mid){dist[j] = dist[t] + w[i] - mid;cnt[j] = cnt[t] + 1;if( ++ count > 2 * n) return true; // trick优化if(cnt[j] >= N) return true;if(!st[j]){q.push(j),st[j] = true;}}}}return false;}int main(){char str[1010];while(cin >> n, n){memset(h, -1, sizeof h);idx = 0;for(int i = 0; i < n; i ++ ){scanf("%s",str);int len = strlen(str);if(len >= 2){int left= (str[0] - 'a') * 26 + str[1] - 'a';int right = (str[len -2 ] - 'a') * 26 + str[len - 1] - 'a';add(left, right, len);}}if(!check(0)) puts("No solution");else {double l = 0, r = 1000;while( r - l > 1e-4){double mid = (l + r)/ 2;if(check(mid)) l = mid;else r = mid;}printf("%.2lf\n",r);}} }

题目链接

https://www.acwing.com/problem/content/1167/

总结

以上是生活随笔为你收集整理的算法提高课-图论-负环-AcWing 1165. 单词环：spfa判正环、二分、01分数规划的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。