文章目錄

• • • 題目分析
    • 題目鏈接

題目分析

來源：acwing

分析：
如何建圖？

這樣建圖。以樣例舉例。起點是前兩個字母，終點是末尾兩個字母，邊權(quán)是字符串的長度。

我們求的是什么呢？

題目要求$\frac{\Sigma 邊權(quán)}{\Sigma 1(點的個數(shù))}$的最大值，這種問題稱為01分?jǐn)?shù)規(guī)劃，通俗點說，就是一堆的和除以一堆的和，要求比值最大。

我們可以通過二分來做，二分啥呢？就是對于一個環(huán)，二分一個mid值，判斷是否滿足$\frac{\Sigma 邊權(quán)}{\Sigma 1(點的個數(shù))}\ge mid$，然后我們就可以來不斷更改二分的區(qū)間，直到找到$\frac{\Sigma 邊權(quán)}{\Sigma 1}$的最大值。

思路確定了，那么具體如何實現(xiàn)呢？

$\frac{\Sigma 邊權(quán)}{\Sigma 1}\ge mid$ 由于這里的邊都是正權(quán)邊，所以可以移項，變成

$$\Sigma 邊權(quán)?mid\times \Sigma 1\ge 0$$

將求和符號提出，亦等價于：

$$\Sigma (邊權(quán)?mid)\ge 0$$
等價于 圖中存在正環(huán)

下面就是默寫spfa判正環(huán)。

當(dāng)然建邊的時候，需要把a(bǔ)b，ba這樣的字母映射到一個整數(shù)（因為每一維都是26個英文字母的一個，這里用26 進(jìn)制來做），是如下這樣做的：

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; // 防止超時，做的優(yōu)化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優(yōu)化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/

總結(jié)

以上是生活随笔為你收集整理的算法提高课-图论-负环-AcWing 1165. 单词环：spfa判正环、二分、01分数规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。