时间戳

首页 > 技术文章 > luogu3358 最长k可重区间集问题 网络流

luogu3358 最长k可重区间集问题 网络流

headboy2002 2018-02-12 15:23 原文

题目大意：

 

关键词：最小费用最大流 不相交路径

如果两个线段重叠了，那我们则把一个线段放在下一层，另一个线段放在上一层。把流量为1的流看作一条线，一条线把位于同一层的线段（互不重叠）都串了起来。最多有k层，则总流量最多为k。问题变成了：每条线如何串串出的线段的长度总和最大？

构图思路1：同一层每一线段都有可能是该层的第一个线段或是该层的最后一个线段。每个位于该线段后面的、不与该线段重合的线段，都是该线段潜在的同一层的下一个线段。因此连接s与每个区间的左端点、每个区间的右端点和T，每个区间的右端点连接每一个不与该线段重合的线段的左端点。为保证总流量最多为k，S向s连容量为k的边。每个线段费用为-线段长度。其余所有边费用0，容量1。

构图思路2：想象有一条竖直的线从左往右扫，穿线段的线也持续从左往右延伸，则竖直线割到的穿线段的线的数量就等于总流量。我们可以在下面再放一层“高速公路”，每一条线如果能在上面几层串线段就在上面几层穿线段，否则就放在“高速公路的一排车道”上往右延伸。具体做法：S点在最前，T点在最后，每个L上的点向其右面的相邻点连一条容量k费用0的边，两个点如果是线段的端点，则连一条容量1，费用-长度的边。

思路2代码：

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

#define LOOP(i,n) for(int i=1; i<=n; i++)
const int MAX_RANGE=510, MAX_NODE = MAX_RANGE*2, MAX_EDGE = MAX_NODE * MAX_NODE, INF = 0x3f3f3f3f;

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, _eCount;
    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)
    {
        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 totRange, totLayer, left[MAX_RANGE], right[MAX_RANGE],
        idMatchP[MAX_NODE], sId, tId, id = 0;
    static map<int, int> pMatchId;
    static set<int> pVis;
    scanf("%d%d", &totRange, &totLayer);
    memset(idMatchP, 0, sizeof(idMatchP));
    memset(left, 0, sizeof(left));
    memset(right, 0, sizeof(right));
    LOOP(i, totRange)
    {
        scanf("%d%d", &left[i], &right[i]);
        if (!pVis.count(left[i]))
        {
            idMatchP[++id] = left[i];
            pVis.insert(left[i]);
        }
        if (!pVis.count(right[i]))
        {
            idMatchP[++id] = right[i];
            pVis.insert(right[i]);
        }
    }
    sId = id + 1;
    tId = id + 2;
    g.Init(tId, sId, tId);
    sort(idMatchP + 1, idMatchP + id + 1);
    LOOP(i, id)
        pMatchId.insert(pair<int, int>(idMatchP[i], i));
    LOOP(i, totRange)
        g.Build(pMatchId[left[i]], pMatchId[right[i]], 1, left[i] - right[i]);
    for (int i = 1; i < id; i++)
        g.Build(i, i + 1, totLayer, 0);
    g.Build(sId, 1, totLayer, 0);
    g.Build(id, tId, totLayer, 0);
    g.Proceed();
    printf("%d\n", -g.TotCost);
    return 0;
}

 

反思：做网络流的题时，网络流的含义应当清楚。思路多点“广度搜索”。

推荐阅读