Description
给定实直线L 上n 个开区间组成的集合I，和一个正整数k，试设计一个算法，从开区间集合I 中选取出开区间集合S属于I，使得在实直线L 的任何一点x，S 中包含点x 的开区间个数不超过k，且sum(|z|)z属于S，达到最大。这样的集合S称为开区间集合I的最长k可重区间集。sum(|z|) z属于S称为最长k可重区间集的长度。对于给定的开区间集合I和正整数k，计算开区间集合I的最长k可重区间集的长度。
Solution
1.离散化 然后从每个点i向i+1连一条流量为INF，费用为0的边
2.对于每个区间，从l[i]到r[i]连一条流量为1，费用为长度的边
3.分别从s向第一个点、最后一个点到t连流量为k，费用为0的边
跑最大费用最大流~
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> #define INF 0x3f3f3f3f using namespace std; int s,t,n,k,head[1005],cnt=0,a[505],b[505],c[1005],tot=0; int dis[1005],f[1005],pre[1005]; bool inq[1005]; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } struct Node { int next,from,to,cap,w; }Edges[500005]; void addedge(int u,int v,int c,int w) { Edges[cnt].next=head[u]; head[u]=cnt; Edges[cnt].from=u,Edges[cnt].to=v; Edges[cnt].w=w; Edges[cnt++].cap=c; } void insert(int u,int v,int c,int w) { addedge(u,v,c,w); addedge(v,u,0,-w); } queue<int>q; int MCMF() { int flow=0,cost=0; while(1) { memset(dis,-1,sizeof(dis)); memset(f,0,sizeof(f)); q.push(s),pre[s]=-1,inq[s]=1,dis[s]=0,f[s]=INF; while(!q.empty()) { int u=q.front(); q.pop(),inq[u]=0; for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(Edges[i].cap>0&&dis[v]<dis[u]+Edges[i].w) { dis[v]=dis[u]+Edges[i].w; f[v]=min(f[u],Edges[i].cap); pre[v]=i; if(!inq[v])q.push(v),inq[v]=1; } } } if(!f[t])break; flow+=f[t],cost+=dis[t]*f[t]; int p=t; while(pre[p]!=-1) { Edges[pre[p]].cap-=f[t]; Edges[pre[p]^1].cap+=f[t]; p=Edges[pre[p]].from; } } return cost; } int main() { memset(head,-1,sizeof(head)); n=read(),k=read(); for(int i=1;i<=n;i++) { a[i]=read(),b[i]=read(); if(a[i]>b[i])swap(a[i],b[i]); c[++tot]=a[i],c[++tot]=b[i]; } sort(c+1,c+1+tot); tot=unique(c+1,c+1+tot)-c-1; for(int i=1;i<=n;i++) { int len=b[i]-a[i]; a[i]=lower_bound(c+1,c+1+tot,a[i])-c; b[i]=lower_bound(c+1,c+1+tot,b[i])-c; insert(a[i],b[i],1,len); } s=0,t=tot+1; insert(s,1,k,0),insert(tot,t,k,0); for(int i=1;i<tot;i++) insert(i,i+1,INF,0); printf("%d ",MCMF()); return 0; }