luogu P3358 最长k可重区间集问题

网络流建图好难，这题居然是网络流(雾，一般分析来说，有限制的情况最大流情况可以拆点通过capacity来限制，比如只使用一次，把一个点拆成入点出点，capacity为1即可，这题是限制最大k重复，可以联想到最大流问题，设源点汇点，限制的k就是其最大的capacity，其最大流一定<=k，跑出来一定满足条件，但如何计算长度呢，就使用费用流吧，最大费用流就把边权取反即可，我们不知道输入的数据范围，只知道个数，就离散化一下，每个区间只能选一次，就对离散化后的l对r连一条capacity为1，权为-len的边，源点对1连一条capacity为k的边，n对汇点连一条capacity为k的边，因为判断是否重复是从头到尾，那么源点汇点就分别连接头尾，但是这样连图不一定保证每个点都考虑进去了，可能会出现图不连通的情况，题目是开区间，那么(i,i+1)和(i+1,i+2)一定是没有交点的，就对i与i+1连一条capacity为无穷，权为0的边，这样就能保证图连通且不会影响到答案，因为如果有断层，其会顺着往下搜索，权为0，capacity为无穷，对答案无影响

#include<bits/stdc++.h>

using namespace std;

#define lowbit(x) ((x)&(-x))

typedef long long LL;

const int maxm = 5e3+;

const int INF = 0x3f3f3f3f;

struct edge{

    int u, v, cap, flow, cost, nex;

} edges[maxm];

struct Points{

    int l, r, len;

} point[];

int head[maxm], cur[maxm], cnt, fa[], d[], n, allx[];

bool inq[];

void init() {

    memset(head, -, sizeof(head));

}

void add(int u, int v, int cap, int cost) {

    edges[cnt] = edge{u, v, cap, , cost, head[u]};

    head[u] = cnt++;

}

void addedge(int u, int v, int cap, int cost) {

    add(u, v, cap, cost), add(v, u, , -cost);

}

bool spfa(int s, int t, int &flow, LL &cost) {

    for(int i = ; i <= ((n<<)|); ++i) d[i] = INF; //init()

    memset(inq, false, sizeof(inq));

    d[s] = , inq[s] = true;

    fa[s] = -, cur[s] = INF;

    queue<int> q;

    q.push(s);

    while(!q.empty()) {

        int u = q.front();

        q.pop();

        inq[u] = false;

        for(int i = head[u]; i != -; i = edges[i].nex) {

            edge& now = edges[i];

            int v = now.v;

            if(now.cap > now.flow && d[v] > d[u] + now.cost) {

                d[v] = d[u] + now.cost;

                fa[v] = i;

                cur[v] = min(cur[u], now.cap - now.flow);

                if(!inq[v]) {q.push(v); inq[v] = true;}

            }

        }

    }

    if(d[t] == INF) return false;

    flow += cur[t];

    cost += 1LL*d[t]*cur[t];

    for(int u = t; u != s; u = edges[fa[u]].u) {

        edges[fa[u]].flow += cur[t];

        edges[fa[u]^].flow -= cur[t];

    }

    return true;

}

int MincostMaxflow(int s, int t, LL &cost) {

    cost = ;

    int flow = ;

    while(spfa(s, t, flow, cost));

    return flow;

}

void run_case() {

    init();

    int l, r, k, xcnt = ;

    cin >> n >> k;

    for(int i = ; i <= n; ++i) {

        cin >> l >> r;

        allx[++xcnt] = l, allx[++xcnt] = r, point[i] = Points{l, r, r-l};

    }

    sort(allx+,allx++xcnt);

    int len = unique(allx+,allx++xcnt)-allx;

    for(int i = ; i <= n; ++i) {

        point[i].l = lower_bound(allx+,allx+len,point[i].l)-allx;

        point[i].r = lower_bound(allx+,allx+len,point[i].r)-allx;

    }

    for(int i = ; i < len-; ++i)

        addedge(i, i+, INF, );

    int s = , t = len;

    for(int i = ; i <= n; ++i) {

        addedge(point[i].l, point[i].r, , -point[i].len);

    }

    addedge(s, , k, ), addedge(len-, t, k, );

    LL cost = ;

    MincostMaxflow(s, t, cost);

    cout << -cost;

}

int main() {

    ios::sync_with_stdio(false), cin.tie();

    run_case();

    cout.flush();

    return ;

}