考虑把一条线段转化成一个点

懵逼的 题目

传送至 Luogu

扯淡的 题解

不会, 看的书,
显然这么大的坐标范围而线段数却并不多, 所以需要离散化端点, 注意这个题的线段是开区间比较恶心人, 需要判断两个端点的坐标相同的时候端点是左端点还是右端点

然后考虑连边, 像下图一样:

  • 给原先在一个线段上的两个端点两边, 容量为1, cost为线段的长度
  • 给相邻的两个端点连边, 容量为INF, cost = 0
  • s连到最左边的端点上, 容量为k, cost = 0, t连在最右边的端点上, 容量为INF, cost = 0

连边

解释:
选一条线段就一定会选上她的两个端点, 所以对于一条线段, 都有选一条和不选两种艹作,
所以一条线段上的两个端点之间连边的容量为1, 选了这个线段就可以得到对答案有cost的贡献
相邻的两个端点连容量为0的边就是可以跳过这条边
显然对于覆盖点的次数, 线段端点被覆盖的次数是最多的(先看成闭区间), 所以只要保证每一个端点被选的次数不超过k次就可以了, 而上面这样连边, 一定会保证在增广一次后, 经过的线段都是不相交的, 因为边的方向都是向右, 选了一条线段, 左端点在这条线段右端点左边的点就都不会在这次增广中被选中了, 而一次增广最多只会增加1单位的流量, 所以s出发的边容量为k就保证了没有覆盖数超过k的端点, 也就没有覆盖数超过k的点…

Emmmm…差不多就是酱

但你以为就结束了嘛…
这个题…首先数据有左端点在右端点之后输入的…还有重复的线段…Emmmmmmmm….

沙茶的 代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXD (500 + 5)
#define MAXN (MAXD << 1)
#define MAXM (MAXN << 3)
#define INF (0x7ffffff)
#define rev(a) (((a - 1) ^ 1) + 1)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define mabs(a) ((a) > 0 ? (a) : (-(a)))
#define swap(a, b) {int t = a; a = b; b = t;}
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
    int from;
    int to;
    int next;
    int cap;
    int flow;
    int cost;
    edg(){}
    edg(int a, int b, int c, int d, int e, int f): from(a), to(b), next(c), cap(d), flow(e), cost(f) {}
}b[MAXM << 1];
int g[MAXN];
int cntb = 0;

struct node
{
    int wz;
    int bh;
    int cost;
    bool isl;
    int ri;
    node(){}
    node(int a, int b, int c, bool d): wz(a), bh(b), cost(c), isl(d) {}
}a[MAXD << 1];

int xdn;
int ans;
int pre[MAXN];
int k;
bool cmp(node, node);
void adn(int, int, int, int);
void init();
void solve();
int spfa();
int main()
{
    scanf("%d%d", &xdn, &k);
    pair<int, int> youdu[MAXD];
    for (int i = 1; i <= xdn; i++)
    {
        int srx, sry;
        scanf("%d%d", &srx, &sry);
        if (sry < srx)
            swap(srx, sry);
        youdu[i] = make_pair(srx, sry);
    }
    xdn = unique(youdu + 1, youdu + xdn + 1) - youdu;
    for (int i = 1; i <= xdn; i++)
    {
        int srx = youdu[i].first;
        int sry = youdu[i].second;
        a[i] = node(srx, i, sry - srx, true);
        a[i + xdn] = node(sry, i, sry - srx, false);
    }
    init();
    solve();
    printf("%d\n", ans);
    return 0;
}
bool cmp(node x, node y)
{
    if (x.wz == y.wz)
    {
        if (x.isl)
        {
            return !y.isl;
        }
        else
        {
            return y.isl;
        }
    }
    return x.wz < y.wz;
}
void adn(int from, int to, int cap, int cost)
{
    b[++cntb] = edg(from, to, g[from], cap, 0, cost);
    g[from] = cntb;
}
void init()
{
    sort(a + 1, a + (xdn << 1), cmp);
    int bh[MAXD];
    adn(s, 1, k, 0);
    adn(1, s, 0, 0);
    for (int i = 1; i <= (xdn << 1); i++)
    {
        if (a[i].isl)
            bh[a[i].bh] = i;
        else
        {
            adn(bh[a[i].bh], i, 1, a[i].cost);
            adn(i, bh[a[i].bh], 0, -a[i].cost);
        }
        if (i < (xdn << 1))
        {
            adn(i, i + 1, INF, 0);
            adn(i + 1, i, 0, 0);
        }
        else
        {
            adn(i, t, INF, 0);
            adn(t, i, 0, 0);
        }
    }
}
void solve()
{
    while (true)
    {
        int zl = spfa();
        if (!zl)
            return ;
        for (int i = t; i != s; i = b[pre[i]].from)
        {
            b[pre[i]].flow += zl;
            b[rev(pre[i])].flow -= zl;
            ans += zl * b[pre[i]].cost;
        }
    }
}
int spfa()
{
    bool inq[MAXN];
    int dis[MAXN];
    int at[MAXN];
    memset(inq, false, sizeof(inq));
    memset(dis, 0, sizeof(dis));
    memset(at, 0, sizeof(at));
    queue<int> q;
    q.push(s);
    inq[s] = true;
    at[s] = INF;
    dis[s] = 1;
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        inq[dq] = false;
        for (int i = g[dq]; i; i = b[i].next)
        {
            if (b[i].cap > b[i].flow && dis[b[i].to] < dis[dq] + b[i].cost)
            {
                dis[b[i].to] = dis[dq] + b[i].cost;
                at[b[i].to] = min(at[dq], b[i].cap - b[i].flow);
                pre[b[i].to] = i;
                if (!inq[b[i].to])
                {
                    q.push(b[i].to);
                    inq[b[i].to] = true;
                }
            }
        }
    }
    return at[t];
}

/*
4 2
1 7
6 8
7 10
9 13 
*/

By Cansult

最近状态不佳 要加油了…