loj6227 「网络流 24 题」最长k可重线段集问题

loj6227 「网络流 24 题」最长k可重线段集问题

( 题目描述

给定平面 xor\text{xor}xor上n个开线段组成的集合 I\text{I}I，和一个正整数k,试设计一个算法。

从开线段集合I\text{I}I中选取出开线段集合S∈I\text{S}\in \text{I}S∈I ,

使得在x轴上的任何一点 p\text{p}p ， S\text{S}S 中与直线 x=p\text{x}=\text{p}x=p 相交的开线段个数不超过 k\text{k}k ，

且 ∑z∈S∣z∣\sum_{\text{z} \in \text{S}}|z|∑z∈S∣z∣ 达到最大。

这样的集合 S\text{S}S 称为开线段集合I\text{I}I 的最长 k\text{k}k 可重线段集的长度。

对于任何开线段z\text{z}z ，设其断电坐标为(x0,y0)( x_0 , y_0 )(x0,y0)和 (x1,y1)( x_1 , y_1 )(x1,y1)，

则开线段 z\text{z}z 的长度 ∣z∣|\text{z}|∣z∣定义为： ∣z∣=⌊(x1−x0)2+(y1−y0)2⌋|z| = \lfloor \sqrt{ ( x_1 - x_0 ) ^ 2 + ( y_1 - y_0 )^2 } \rfloor∣z∣=⌊√(x1−x0)2+(y1−y0)2⌋

对于给定的开线段集合 I\text{I}I 和正整数 k\text{k}k ，计算开线段集合 I\text{I}I 的最长 k\text{k}k 可重线段集的长度。 输入格式

文件的第一 行有二 个正整数 n\text{n}n 和 k\text{k}k ，分别表示开线段的 个数和开线段的可重迭数。接下来的 n\text{n}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≤5001\leq n\leq5001≤n≤500

1≤k≤131 \leq k \leq 131≤k≤13

同之前的最长k可重区间集问题 很像

但是这个建图略有不同 不同在哪里 针对这个 开区间(4,4)也是成立的开区间 但是如果我有自环去跑我的spfa 肯定会tle 怎么办 从Leoly那里get一种新的离散化方式qwq 强制把我两个点扩大一下 然后分成奇数和偶数 这样我就可以强制把一个点拆成两个点了 然后做法和之前一样 首先我需要i,i+1之间连Inf的边 这样我就保证了 我不需要从源点向每个线段连边 然后我从一个线段的左端点要向右端点连边 权值为1 费用为长度 这样保证了我这个线段只被使用一次 然后跑最大费用最大流即可 还要限制一下源点到起点的权值为k才可以

#include#include #include#include#include#define inf 0x3f3f3f3f#define N 1100using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}struct node{ int x,y,next,z,c;}data[N*N];inline long long calc(int x1,int y1,int x2,int y2){ return (long long)(x2-x1)*(x2-x1)+(long long)(y2-y1)*(y2-y1);}int num=1,h[N],xx[N],x2[N],yy[N],y2[N],T,pre[N],path[N],n,k,flag[N],qq[N],f[N],w[N];inline void insert1(int x,int y,int z,int c){ data[++num].y=y;data[num].next=h[x];data[num].z=z;data[num].c=c;h[x]=num;data[num].x=x; data[++num].y=x;data[num].next=h[y];data[num].z=0;data[num].c=-c;h[y]=num;data[num].x=y;}inline bool spfa(){ memset(f,128,sizeof(f));memset(flag,0,sizeof(flag));memset(pre,-1,sizeof(pre));queueq;flag[0]=1;f[0]=0;q.push(0); while(!q.empty()){ int x=q.front();flag[x]=0;q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z,c=data[i].c; if (f[x]+c>f[y]&&z){ f[y]=f[x]+c;pre[y]=x;path[y]=i; if (!flag[y]) flag[y]=1,q.push(y); } } }if (pre[T]==-1) return 0;else return 1;}int main(){ freopen("loj.in","r",stdin); n=read();k=read();int tot=0; for (int i=1;i<=n;++i){ xx[i]=read(),yy[i]=read(),x2[i]=read(),y2[i]=read();w[i]=sqrt(calc(xx[i],yy[i],x2[i],y2[i])); xx[i]=xx[i]<<1|1;x2[i]<<=1;qq[++tot]=xx[i];qq[++tot]=x2[i];if (xx[i]>x2[i]) swap(xx[i],x2[i]); }sort(qq+1,qq+tot+1);int nn=unique(qq+1,qq+tot+1)-qq-1;T=nn+1;//printf("%d\n",nn); for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。