luogu2754 星际转移问题网络流

题目大意：地球与月球间有可容纳无限人的太空站，还有在太空站与星球间按周期行驶的、有固定容量的太空船，每一艘太空船从一个太空站驶往任一太空站耗时均为 1。地球上有一定数量的人，问所有人到月球最少需要多少天。

关键词：分层最小费用最大流

最大流：把人群看作流。

分层：人们的最优选择会受到其位于哪一天的影响，因此我们关于时间将整个图分层。估计一下最多能用多少天，就分多少层。人们在太空站内可以呆着，因此每天的太空站要向下一天的太空站连容量∞费用1边。太空船运人，因此太空船前一站向下一天的后一站连容量∞费用1边。人类量固定，从S点向第一天的地球连容量为人数费用0边。任意时刻到达月球均可，从每天的月球向T连容量为无穷费用0边。

最小费用：这里的MCMF有些不同：费用不是单位费用，而是绝对费用；最小费用是每次SPFA所得路径的总费用的最大值，而不是和（否则同一天两群人坐船就被算成了两天）。

#include <cstdio>
#include <cstring>
#include <cassert>
#include <queue>
#include <vector>
using namespace std;
//#define test

#define LOOP(i,n) for(int i=1; i<=n; i++)
#define S(station, day) station + (day - 1) * TotStation
#define R(x, t) (x - 1) % (t) + 1
#define INF 0x3f3f3f3f
const int MAX_SHIP = 25, MAX_STOP = 30, MAX_DAY = 400, MAX_NODE = MAX_STOP * MAX_DAY;

int TotStation, TotShip, TotHuman;
int Cap[MAX_SHIP], Route[MAX_SHIP][MAX_STOP], StopCnt[MAX_STOP];

struct MCMF
{
    struct Node;
    struct Edge;

    struct Node
    {
        Edge *Head, *Prev;
        int Dist, Id;
        bool Inq;
    };

    struct Edge
    {
        int Cap, Cost, OrgCap;
        Node *From, *To;
        Edge *Next, *Rev;
    };


    Node _nodes[MAX_NODE];
    vector<Edge*> _edges;
    int _vCount = 0, _eCount = 0;
    Node *Start, *Sink;
    int TotFlow, TotCost;

    void Init(int n, int sId, int tId)
    {
        _vCount = n;
        _eCount = 0;
        Start = &_nodes[sId], Sink = &_nodes[tId];
        TotFlow = TotCost = 0;
    }

    Edge *NewEdge()
    {
        if (_eCount < _edges.size())
            return _edges[_eCount];
        else
        {
            _edges.push_back(new Edge());
            return _edges[_eCount++];
        }
    }

    Edge* AddEdge(Node *from, Node *to, int cap, int cost)
    {
        Edge *e = NewEdge();
        e->From = from;
        e->To = to;
        e->OrgCap = e->Cap = cap;
        e->Cost = cost;
        e->Next = e->From->Head;
        e->From->Head = e;
        return e;
    }

    void Build(int uId, int vId, int cap, int cost)
    {
        Node *u = uId + _nodes, *v = vId + _nodes;
        u->Id = uId;
        v->Id = vId;
        Edge *edge1 = AddEdge(u, v, cap, cost), *edge2 = AddEdge(v, u, 0, -cost);
        edge1->Rev = edge2;
        edge2->Rev = edge1;
    }

    bool SPFA()
    {
        queue<Node*> q;
        LOOP(i, _vCount)
        {
            _nodes[i].Prev = NULL;
            _nodes[i].Dist = INF;
            _nodes[i].Inq = false;
        }
        Start->Dist = 0;
        q.push(Start);
        while (!q.empty())
        {
            Node *u = q.front();
            q.pop();
            //printf("SPFA %d Dist %d
", u->Id, u->Dist);
            u->Inq = false;
            for (Edge *e = u->Head; e; e = e->Next)
            {
                if (e->Cap && u->Dist + e->Cost < e->To->Dist)
                {
                    e->To->Dist = u->Dist + e->Cost;
                    e->To->Prev = e;
                    if (!e->To->Inq)
                    {
                        e->To->Inq = true;
                        q.push(e->To);
                    }
                }
            }
        }
        return Sink->Prev;
    }

    void Proceed()
    {
        while (SPFA())
        {
            assert(Sink->Dist != INF);
            int minFlow = INF, curCost = 0;
            for (Edge *e = Sink->Prev; e; e = e->From->Prev)
                minFlow = min(minFlow, e->Cap);
            TotFlow += minFlow;
            for (Edge *e = Sink->Prev; e; e = e->From->Prev)
            {
                e->Cap -= minFlow;
                e->Rev->Cap += minFlow;
                curCost += e->Cost;
            }
            TotCost = max(TotCost, curCost);
        }
    }
}g;


int Proceed(int totDay)
{
    int sId = TotStation*totDay + 1, tId = TotStation*totDay + 2;
    g.Init(tId, sId, tId);
    g.Build(sId, 2, TotHuman, 0);
    for (int i = 1; i < sId; i += TotStation)
        g.Build(i, tId, INF, 0);
    LOOP(station, TotStation)
        LOOP(day, totDay - 1)
            g.Build(S(station, day), S(station, day + 1), INF, 1);
    LOOP(ship, TotShip)
        LOOP(day, totDay - 1)
        g.Build(S(Route[ship][R(day, StopCnt[ship])], day), S(Route[ship][R(day + 1, StopCnt[ship])], day + 1), Cap[ship], 1);
    g.Proceed();
    if (g.TotFlow < TotHuman)
        return 0;
    return g.TotCost;
}

int main()
{
#ifdef _DEBUG
    freopen("c:\noi\source\input.txt", "r", stdin);
#endif
    scanf("%d%d%d", &TotStation, &TotShip, &TotHuman);
    TotStation += 2;
    LOOP(i, TotShip)
    {
        scanf("%d%d", i + Cap, i + StopCnt);
        LOOP(j, StopCnt[i])
        {
            scanf("%d", &Route[i][j]);
            Route[i][j] += 2;
        }
    }
    printf("%d
", Proceed(MAX_DAY));
    return 0;
}

View Code

注意：

1.要让包括星球在内的太空站的编号从1开始，否则容易晕。

2.最大值不要卡着边设。

luogu2754 星际转移问题 网络流

luogu2754 星际转移问题网络流