网络流24题-最长k可重线段集问题

时间：2023-12-21 16:42:32

最长k可重线段集问题

时空限制1000ms / 128MB

题目描述

给定平面 x−O−y 上 n 个开线段组成的集合 I，和一个正整数 k 。试设计一个算法，从开线段集合 I 中选取出开线段集合 S⊆I ,使得在 x 轴上的任何一点 p，S 中与直线 x=p 相交的开线段个数不超过 k，且∑​∣z∣达到最大。这样的集合 S 称为开线段集合 I 的最长 k 可重线段集。∑​∣z∣ 称为最长 k 可重线段集的长度。

对于任何开线段 z，设其断点坐标为 (x0​,y0​) 和 (x1​,y1​)，则开线段 z 的长度 ∣z∣ 定义为：|z|=⌊sqrt{(x1-x0)^2+(y1-y0)^2}⌋

对于给定的开线段集合 I 和正整数 k，计算开线段集合 I 的最长 k 可重线段集的长度。

输入输出格式

输入格式：

文件的第一 行有 2 个正整数 n 和 k，分别表示开线段的个数和开线段的可重叠数。

接下来的 n 行，每行有 4 个整数，表示开线段的 2 个端点坐标。

输出格式：

程序运行结束时，输出计算出的最长 k 可重线段集的长度。

输入输出样例

输入样例： 
4 2

1 2 7 3

6 5 8 3

7 8 10 5

9 6 13 9
输出样例： 
17

说明

1≤n≤500

1≤k≤13

题目链接：https://www.luogu.org/problemnew/show/P3357

最大权不相交路径。和这一题很类似。但是这一题会出现线段垂直x轴的情况，这样就会出现自环，而且是负环，所以直接跑费用流会有问题。因此要对每一个点进行拆点，拆成1号点和2号点，具体连边操作为：每个点和下一个点之间连一条费用为0，容量为INF的边。对于某线段，设其在x轴上投影的左右端点为点u和点v，若u=v，则在这个点的1号点和2号点之间连一条费用为边权，容量为1的边，否则在u的2号点和v的1号点之间连一条边。 
#include<bits/stdc++.h>

#define INF LLONG_MAX/2

#define N 3005

using namespace std;

struct ss

{

    int u,v,next;

    long long flow,cost;

};

ss edg[N*];

int head[N],now_edge=;

void addedge(int u,int v,long long flow,long long cost)

{

     edg[now_edge]=(ss){u,v,head[u],flow,cost};

    head[u]=now_edge++;

    edg[now_edge]=(ss){v,u,head[v],,-cost};

    head[v]=now_edge++;

}

int spfa(int s,int t,long long &flow,long long &cost)

{

    int vis[N]={};

    vis[s]=;

    queue<int>q;

    q.push(s);

    long long dis[N];

    for(int i=;i<N;i++)dis[i]=INF;

    dis[s]=;

    int pre[N]={};

    long long addflow[N]={};

    addflow[s]=INF;

    while(!q.empty())

    {

        int now=q.front();

        q.pop();

        vis[now]=;

        for(int i=head[now];i!=-;i=edg[i].next)

        {

            ss e=edg[i];

            if(e.flow>&&dis[e.v]>dis[now]+e.cost)

            {

                dis[e.v]=dis[now]+e.cost;

                pre[e.v]=i;

                addflow[e.v]=min(e.flow,addflow[now]);

                if(!vis[e.v])

                {

                    q.push(e.v);

                    vis[e.v]=;

                }

            }

        }

    }

    if(dis[t]==INF)return ;

    flow+=addflow[t];

    cost+=addflow[t]*dis[t];

    int now=t;

    while(now!=s)

    {

        edg[pre[now]].flow-=addflow[t];

        edg[pre[now]^].flow+=addflow[t];

        now=edg[pre[now]].u;

    }

    return ;

}

void mcmf(int s,int t,long long &flow,long long &cost)

{

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

}

void init()

{

    now_edge=;

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

}

long long x[N][];

long long LSH[N];

int size_lsh=;

int f(long long x)

{

    return lower_bound(LSH,LSH+size_lsh,x)-LSH+;

}

long long dist(long long x[])

{

double now=(x[]-x[])*(x[]-x[])+(x[]-x[])*(x[]-x[]);

now=sqrt(now);

return (long long)now;

}

int main()

{

    init();

    int n,k;

    scanf("%d %d",&n,&k);

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

    for(int j=;j<;j++)

     {

        scanf("%lld",&x[i][j]);

        if(j%==)LSH[size_lsh++]=x[i][j];

    }

    sort(LSH,LSH+size_lsh);

    size_lsh=unique(LSH,LSH+size_lsh)-LSH;

    int s=size_lsh*+,t=s+;

    for(int i=;i<size_lsh*;i++)addedge(i,i+,INF,);

    addedge(s,,k,);

    addedge(size_lsh*,t,INF,);

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

    {

        int u=min(f(x[i][]),f(x[i][])),v=max(f(x[i][]),f(x[i][]));

        long long w=dist(x[i]);

        if(u!=v)addedge(u*,v*-,,-w);

        else

        addedge(*u-,*v,,-w);

    }

    long long flow=,cost=;

    mcmf(s,t,flow,cost);

    printf("%lld\n",-cost);

    return ;

}

相关文章