Luogu 3778 [APIO 2017] 商旅

• • • • • 傳送門
        • 思路
        • 參考代碼

傳送門

思路

  唉，我太弱了，什麼都不會。看到這道題就想到了二分答案找負環，但是怎麼做呢？完全不會。唉，我太弱啦！

  先注意題目中說可以重複經過點和邊，這啟示我們：如果使用一般的算法，很難做到處理可以重複走的情況。另外，當務之急是要處理出走一個環的最大收益，但是我們不知道到底該怎麼在環上走，問題一下就變得複雜了起來。

  觀察發現，一個環路一定是這樣走的：在一個起點買一件物品，走到一個地方把它賣掉，再買一個物品，再走到一個地方把它賣掉……但是有可能有部分地方我們沒有買物品啊，很簡單，隻需要增加一種買入和賣出價都為 0 0 的“空物品”就好了。

  現在，如果我們知道了買入點和賣出點，就相當于知道了最大收益 ss（應該注意到，這個收益不應小于 0 0 ）。另外，如果我們知道了兩個點，那它們之間的最短路徑 ll 是确定的。至此，問題終于變成了經典的求環的最大平均邊權問題了。隻需要二分答案，然後将式子 ∑s∑l=ans ∑ s ∑ l = a n s 變成 ∑s−∑l×ans=0 ∑ s − ∑ l × a n s = 0 ，再判斷負圈就好了。

  具體地說，如果有 ∑s−∑l×ans≥0 ∑ s − ∑ l × a n s ≥ 0 ，就相當于是說存在一個環使得 ∑s∑l≥ans ∑ s ∑ l ≥ a n s ，即 ans a n s 可以更大。是以我們的任務是判斷是否存在正圈。方法是把所有邊權取負，然後求負圈就可以了。（想一想，為什麼不能把不等号反号并改變二分方向然後直接求負圈，而必須求是否存在正圈）

參考代碼

#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 = ; 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 *  - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[]; int length = ;
    if (x < ) putchar('-'); else x = -x;
    do buffer[length++] = -(x % ) + '0'; while (x /= );
    do putchar(buffer[--length]); while (length);
}

LL INF;
const int maxn = ;
const int maxk = ;
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, -, 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 = ;
        memset(head, -, 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 = ; }
    Queue() { clear(); }
    void push(int x) { c[tail] = x; tail = tail +  >= maxn ?  : tail + ; }
    void pop() { head = head +  >= maxn ?  : head + ; }
    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, , sizeof(enter));
    std::fill(dis, dis +  + n, );
    q.clear();
    q.push(s);
    inQ[s] = true;
    dis[s] = ;
    enter[s] = ;
    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 = ; i <= n; i++)
        for (int j = ; j <= n; j++)
            if (i != j)
                T.addEdge(i, j, -(earn[i][j] - path[i][j] * s));

    return SPFA(T, , dis);
}

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

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

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

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

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

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

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