luogu4012 深海机器人问题 网络流

关键词：最小费用最大流

题目大意：海底是个网格，每个网格边有一定价值的海底化石。每个路线可经过无限个机器人，但上面的化石只能采一次。机器人可沿网格边向东或向北移动。给定机器人起点和终点位置及所能容纳的机器人数，求能获得的最大价值。

网络流：把一个机器人运动的轨迹看作一个流量为1的流。

化石只能采一次，我们想到建立一条容量为1的边，价值为-化石价值。以后该路线可经过无限个机器人，我们想到建立一条容量为∞的边，价值为0。S连起点，终点连T，容量为其所能容纳的机器人数。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cassert>
using namespace std;

#define LOOP(i, n) for(int i=1; i<=n; i++)
#define ID(col, row) row * (lastCol + 1) + col + 1
const int MAX_NODE = 20 * 20, MAX_EDGE = MAX_NODE*MAX_NODE * 4, INF = 0x3f3f3f3f, MAX_ROW = 20, MAX_COL = 20;

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;
        Edge(int cap, int cost, Node *from, Node *to, Edge *next) :Cap(cap), OrgCap(cap), Cost(cost), From(from), To(to), Next(next) {}
    };


    Node _nodes[MAX_NODE];
    Edge *_edges[MAX_EDGE];
    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* AddEdge(Node *from, Node *to, int cap, int cost)
    {
        Edge *e = _edges[++_eCount] = new Edge(cap, cost, from, to, from->Head);
        e->From->Head = e;
        return e;
    }

    void Build(int uId, int vId, int cap, int cost)
    {
        //printf("%d->%d
", uId, vId);
        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();
            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;
            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;
                TotCost += minFlow * e->Cost;
            }
        }
    }
}g;

int main()
{
#ifdef _DEBUG
    freopen("c:\noi\source\input.txt", "r", stdin);
#endif
    int totStart, totTarget, lastCol, lastRow,
        row, col, horiVal, vertVal, robotCnt;
    scanf("%d%d%d%d", &totStart, &totTarget, &lastRow, &lastCol);
    int sId = ID(lastCol, lastRow) + 1, tId = ID(lastCol, lastRow) + 2;
    g.Init(tId, sId, tId);
    for (int row = 0; row <= lastRow; row++)
        for (int col = 1; col <= lastCol; col++)
        {
            scanf("%d", &horiVal);
            g.Build(ID((col - 1), row), ID(col, row), INF, 0);
            g.Build(ID((col - 1), row), ID(col, row), 1, -horiVal);
        }
    for (int col = 0; col <= lastCol; col++)
        for (int row = 1; row <= lastRow; row++)
        {
            scanf("%d", &vertVal);
            g.Build(ID(col, (row - 1)), ID(col, row), INF, 0);
            g.Build(ID(col, (row - 1)), ID(col, row), 1, -vertVal);
        }
    LOOP(i, totStart)
    {
        scanf("%d%d%d", &robotCnt, &row, &col);
        g.Build(sId, ID(col, row), robotCnt, 0);
    }
    LOOP(i, totTarget)
    {
        scanf("%d%d%d", &robotCnt, &row, &col);
        g.Build(ID(col, row), tId, robotCnt, 0);
    }
    g.Proceed();
    printf("%d
", -g.TotCost);
    return 0;
}

注意：宏替换写函数时，对其所操作的参数尽量打括号，否则会出现运算顺序问题。