Menu
Article

POJ 3621 Sightseeing Cows

NodeKey

NodeKey

• 3 min read

分数划分之最优比例环。
分数划分中比较常见的限制之一，在图中筛选的必须是一个环。

本来在入门题的时候对于以下转换公式有考虑过这样的一个问题：

$ \sum \left( \left( a_{i}-L\times b_{i}\right) \times x_{i}\right) $

为什么只需要考虑 ( \left( a_{i}-L\times b_{i}\right) ) 与 ( 0 ) 之间的关系，而不用去管( x_i )了呢？明明取舍( x_i )也是对答案会造成影响的。

而实际上，举个例子，对于最优比例环来说，成不成环就是一个主要的筛选的过程。然后再是对于二分的值( L )，如果对于当前( L) 仍有可提升空间。若仍有提升空间，就说明( L)可以更大。

不知不觉就跟学习资料上说的一模一样了
也许我自己也没有深刻理解，但还是有写意会了吧。

题意：
给你一张图，图上的每个节点和边都有权值。要你找出一个环，使得点权和 – 边权和最大。

思路：
我们要最大化 点权和 – 边权和，那么我们二分的时候就要找一个 ( L ) ，使得转化函数大于0。
因为对于一个环来说，他的点数与边数是相同的，所以我们在边权上处理一下就转化成了一个找正环的判定。
考虑到 spfa 只能用来求负环，那么就把边权取反即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const double eps = 1e-5;
const int maxn = 1e3 + 5;
const int maxm = 5e3 + 5;

int n, m, idx;
int val[maxn];
int head[maxn];

struct node {
    int to, weight;
    int next;
} edges[maxm << 1];

void addEdge(int u, int v, int w)
{
    edges[idx] = (node){ v, w, head[u] };
    head[u] = idx++;
}

queue<int> que;

bool spfa(int st, double key)
{
    while (!que.empty())
        que.pop();
    bool inq[maxn];
    double dis[maxn];
    int cnt[maxn];
    fill(cnt, 0), fill(inq, false);
    each(i,n+1) dis[i] = 0x3f3f3f3f;
    dis[st] = 0, inq[st] = true, cnt[st] = 1;
    que.push(st);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        inq[u] = false;
        for (int id = head[u]; ~id; id = edges[id].next) {
            int v = edges[id].to;
            double w = 1.0 * edges[id].weight * key - val[v];
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!inq[v]) {
                    inq[v] = true;
                    que.push(v);
                    if (++cnt[v] >= n)
                        return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    int u, v, w;
    while (scanf("%d %d", &n, &m) != EOF) {
        fill(head, -1), idx = 0;
        range(i, 1, n) scanf("%d", val + i);
        each(i, m)
        {
            scanf("%d %d %d", &u, &v, &w);
            addEdge(u, v, w);
        }
        double l = 0, r = 2000, mid;
        while (l + eps < r) {
            mid = (l + r) / 2;
            if (spfa(1, mid))
                l = mid;
            else
                r = mid - eps;
        }
        printf("%.2f\n", l);
    }
    return 0;
}
Share