andyli

题解 UVA11090 【Going in Cycle!!】
使用二分法求解。对于一个猜测值$M$,只需要判断是否存在平均值小于$M$的回路。如何判断呢?假设存在一个包含$k$...
扫描右侧二维码阅读全文
25
2019/06

题解 UVA11090 【Going in Cycle!!】

使用二分法求解。对于一个猜测值$M$,只需要判断是否存在平均值小于$M$的回路。如何判断呢?假设存在一个包含$k$条边的回路,回路上各条边的权值为$w_1,w_2,...,w_k$,那么平均值小于$M$意味着$w_1+w_2+...+w_k<k*mid$即:
$$(w_1-M)+(w_2-M)+(w_3-M)+...+(w_k-M)<0$$
换句话说,只要把每条边$(a,b)$的权值$w(a,b)$变成$w(a,b)-M$,再判断新图中是否有负环即可。代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 51, maxm = 2501;

struct Edge
{
    int next, to;
    double w;
    Edge(int next = 0, int to = 0, double w = 0.0) : next(next), to(to), w(w) {}
} edges[maxm << 1];
int head[maxn], inqcnt[maxn], n, m, cnt;
double dis[maxn];
bool vis[maxn];
void AddEdge(int u, int v, double w)
{
    edges[++cnt] = Edge(head[u], v, w);
    head[u] = cnt;
}
bool SPFA()
{
    memset(vis, 0, sizeof(vis));
    memset(inqcnt, 0, sizeof(inqcnt));
    queue<int> q;
    for (int i = 1; i <= n; i++)
        dis[i] = 0, q.push(i);
    vis[1] = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; i; i = edges[i].next)
        {
            int v = edges[i].to;
            double t = dis[u] + edges[i].w;
            if (dis[v] > t)
            {
                dis[v] = t;
                if (!vis[v])
                {
                    q.push(v);
                    vis[v] = true;
                    if (++inqcnt[v] > n)
                        return true;
                }
            }
        }
    }
    return false;
}
bool test(double x)
{
    for (int i = 1; i <= cnt; i++)
        edges[i].w -= x; // 修改权值
    bool ans = SPFA();
    for (int i = 1; i <= cnt; i++)
        edges[i].w += x; // 恢复权值
    return ans;
}
int main()
{
    int T;
    scanf("%d", &T);
    for (int kase = 1; kase <= T; kase++)
    {
        scanf("%d%d", &n, &m);
        memset(head, 0, sizeof(head));
        cnt = 0;
        double L = 0.0, R = 0; // R为最大权值
        while (m--)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            R = max(R, w * 1.0);
            AddEdge(u, v, w);
        }
        printf("Case #%d: ", kase);
        if (!test(R + 1))
            printf("No cycle found.\n"); // 如果有负环,平均权值一定小于R+1
        else
        {
            while (R - L > 1e-3)
            {
                double M = (L + R) / 2;
                if (test(M))
                    R = M;
                else
                    L = M;
            }
            printf("%.2lf\n", L);
        }
    }
    return 0;
}
Last modification:June 25th, 2019 at 11:30 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment