Luogu 3778 [APIO 2017] 商旅

传送门

思路

  唉，我太弱了，什么都不会。看到这道题就想到了二分答案找负环，但是怎么做呢？完全不会。唉，我太弱啦！

  先注意题目中说可以重复经过点和边，这启示我们：如果使用一般的算法，很难做到处理可以重复走的情况。另外，当务之急是要处理出走一个环的最大收益，但是我们不知道到底该怎么在环上走，问题一下就变得复杂了起来。

  观察发现，一个环路一定是这样走的：在一个起点买一件物品，走到一个地方把它卖掉，再买一个物品，再走到一个地方把它卖掉……但是有可能有部分地方我们没有买物品啊，很简单，只需要增加一种买入和卖出价都为 0 0 $0$ 的“空物品”就好了。

  现在，如果我们知道了买入点和卖出点，就相当于知道了最大收益 s$s$$s$（应该注意到，这个收益不应小于 0 0 $0$）。另外，如果我们知道了两个点，那它们之间的最短路径 l$l$$l$ 是确定的。至此，问题终于变成了经典的求环的最大平均边权问题了。只需要二分答案，然后将式子 ∑s∑l=ans ∑ s ∑ l = a n s $\frac {\sum s} {\sum l} = ans$ 变成 ∑s−∑l×ans=0 ∑ s − ∑ l × a n s = 0 $\sum s - \sum l \times ans = 0$，再判断负圈就好了。

  具体地说，如果有 ∑s−∑l×ans≥0 ∑ s − ∑ l × a n s ≥ 0 $\sum s - \sum l \times ans \ge 0$，就相当于是说存在一个环使得 ∑s∑l≥ans ∑ s ∑ l ≥ a n s $\frac {\sum s} {\sum l} \ge ans$，即 ans a n s $ans$ 可以更大。所以我们的任务是判断是否存在正圈。方法是把所有边权取负，然后求负圈就可以了。（想一想，为什么不能把不等号反号并改变二分方向然后直接求负圈，而必须求是否存在正圈）

参考代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
}

LL INF;
const int maxn = 105;
const int maxk = 1005;
int n, m, k;
int b[maxn][maxk];
int s[maxn][maxk];

struct Graph
{
    struct Edge
    {
        int to;
        double cost;
        int next;
    } edges[maxn * maxn];
    int i;
    int head[maxn];
    Graph() : i() { memset(head, -1, sizeof(head)); }
    void addEdge(int from, int to, double cost)
    {
        edges[i].to = to;
        edges[i].cost = cost;
        edges[i].next = head[from];
        head[from] = i;
        i++;
    }
    void clear()
    {
        i = 0;
        memset(head, -1, sizeof(head));
    }
#define idx(G) idx_##G
#define wander(G, node) for (int idx(G) = G.head[node]; ~idx(G); idx(G) = G.edges[idx(G)].next)
#define DEF(G) const Graph::Edge& e = G.edges[idx(G)]; int to = e.to; double cost = e.cost
} G;

LL earn[maxn][maxn];
double path[maxn][maxn];

struct Queue
{
    int c[maxn];
    int head, tail;
    void clear() { head = tail = 0; }
    Queue() { clear(); }
    void push(int x) { c[tail] = x; tail = tail + 1 >= maxn ? 0 : tail + 1; }
    void pop() { head = head + 1 >= maxn ? 0 : head + 1; }
    int front() { return c[head]; }
    bool empty() { return head == tail; }
} q;
bool inQ[maxn];
int enter[maxn];
bool SPFA(const Graph& G, int s, double dis[maxn])
{
    memset(inQ, false, sizeof(inQ));
    memset(enter, 0, sizeof(enter));
    std::fill(dis, dis + 1 + n, 1e20);
    q.clear();
    q.push(s);
    inQ[s] = true;
    dis[s] = 0;
    enter[s] = 1;
    while (!q.empty())
    {
        int from = q.front();
        q.pop();
        inQ[from] = false;
        wander(G, from)
        {
            DEF(G);
            if (dis[from] + cost < dis[to])
            {
                dis[to] = dis[from] + cost;
                if (++enter[to] >= n) return true;
                if (!inQ[to])
                {
                    q.push(to);
                    inQ[to] = true;
                }
            }
        }
    }
    return false;
}

Graph T;
double dis[maxn];
bool check(double s)
{
    T.clear();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j)
                T.addEdge(i, j, -(earn[i][j] - path[i][j] * s));

    return SPFA(T, 1, dis);
}

void run()
{
    memset(&INF, 0x3f, sizeof(INF));

    n = readIn();
    m = readIn();
    k = readIn();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++)
        {
            b[i][j] = readIn();
            s[i][j] = readIn();
        }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            LL& t = earn[i][j];
            t = 0;
            for (int l = 1; l <= k; l++)
                if (b[i][l] != -1 && s[j][l] != -1)
                    t = std::max(t, (LL)s[j][l] - b[i][l]);
        }
    }

    for (int i = 1; i <= m; i++)
    {
        int from = readIn();
        int to = readIn();
        int cost = readIn();
        G.addEdge(from, to, cost);
    }

    for (int i = 1; i <= n; i++)
        SPFA(G, i, path[i]);

    double l = 0, r = 1e11;
    while (r - l >= 1e-2)
    {
        double mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    printOut(r);
}

int main()
{
    run();
    return 0;
}