关键词：最小费用最大流

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

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

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

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define LOOP(i, n) for(int i=1; i<=n; i++)#define ID(col, row) row * (lastCol + 1) + col + 1const 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\n", 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
            
              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\n", -g.TotCost); return 0;}
            
           
          
         
        
       
      

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