UVA-11090 Going in Cycle!!

链接

有一张带权有向图，有$n$个点，$m$条边。如果无环则输出”No cycle found.”否则求一个最小的环平均权值。（环平均权值=环上边权值之和/环上边的数量）

分析

我们把上面等式环上边的数量乘到等式的左边，然后再把等式两边同时减去等式的右边，就变成了这样一个形式：

所以我们可以二分答案$ans$，将每条边的边权$w$修改为$w-ans$，用$SPFA$判断是否存在负权回路，若存在则说明有更小的答案，否则反之。

代码


#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 55;
const int maxm = maxn * maxn;
const double INF = 50.0 * 10000000.0;
const double EPS = 1e-8;
class CNode {
   public:
    int x, next;
    double w;
};
int n, m;
int len, h[maxm];
CNode table[maxm];
int cnt[maxn];
double dis[maxn];
double mid, l, r;
bool vis[maxn], Qvis[maxn];
queue<int> Q;
inline void (int u, int v, int w) {
    len++;
    table[len].x = v;
    table[len].w = w;
    table[len].next = h[u];
大专栏  UVA-11090 Going in Cycle!!ass="line">    h[u] = len;
}
inline bool spfa(int s, double x) {
    int p;
    memset(cnt, 0, sizeof(cnt));
    memset(Qvis, 0, sizeof(Qvis));
    for (int i = 1; i <= n; i++) dis[i] = INF;
    while (!Q.empty()) Q.pop();
    Q.push(s);
    dis[s] = 0;
    vis[s] = true;
    Qvis[s] = true;
    cnt[s] = 1;
    while (!Q.empty()) {
        p = Q.front();
        Q.pop();
        Qvis[p] = false;
        for (int i = h[p]; i; i = table[i].next) {
            if (dis[table[i].x] > dis[p] + (table[i].w - x)) {
                dis[table[i].x] = dis[p] + (table[i].w - x);
                if (!Qvis[table[i].x]) {
                    vis[table[i].x] = true;
                    Qvis[table[i].x] = true;
                    Q.push(table[i].x);
                    cnt[table[i].x]++;
                    if (cnt[table[i].x] > n) return true;
                }
            }
        }
    }
    return false;
}
inline bool check(double x) {
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++)
        if (!vis[i] && spfa(i, x)) return true;
    return false;
}
inline void solve(int tcase) {
    int u, v, w;
    len = 0;
    memset(h, 0, sizeof(h));
    printf("Case #%d: ", tcase);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }
    l = 0;
    r = INF;
    while (l < r) {
        mid = (l + r) / 2.0;
        if (check(mid))
            r = mid - EPS;
        else
            l = mid + EPS;
    }
    if (fabs(l - INF) < EPS)
        printf("No cycle found.n");
    else
        printf("%.2fn", l);
}
int main() {
    
    int T;
    scanf("%d", &T);
    for (int tcase = 1; tcase <= T; tcase++) solve(tcase);
    return 0;
}