«问题描述：
«编程任务：
对于给定的开区间集合I和正整数k，计算开区间集合I的最长k可重区间集的长度。
«数据输入：
由文件interv.in提供输入数据。文件的第1 行有2 个正整数n和k，分别表示开区间的
个数和开区间的可重迭数。接下来的n行，每行有2个整数，表示开区间的两个端点坐标。
«结果输出:
程序运行结束时，将计算出的最长k可重区间集的长度输出到文件interv.out中。
输入文件示例 输出文件示例
interv.in
4 2
1 7
6 8
7 10
9 13
interv.out
15
/* 朴素的做法： 把k看作是k条路径，一条路径只能由不重复的区间组成，每个区间只能用一次，然后拆点跑最大费用流。 */ #include<iostream> #include<cstdio> #include<algorithm> #include<queue> #define N 1010 #define inf 1000000000 using namespace std; int head[N],dis[N],inq[N],fa[N],n,k,S,T,cnt=1; struct Node{int l,r;}a[N]; struct node{int v,f,w,pre;}e[N*100]; queue<int> q; void add(int u,int v,int f,int w){ e[++cnt].v=v;e[cnt].f=f;e[cnt].w=w;e[cnt].pre=head[u];head[u]=cnt; e[++cnt].v=u;e[cnt].f=0;e[cnt].w=-w;e[cnt].pre=head[v];head[v]=cnt; } bool spfa(){ for(int i=0;i<=T;i++) dis[i]=inf; dis[S]=0;q.push(S); while(!q.empty()){ int u=q.front();q.pop();inq[u]=0; for(int i=head[u];i;i=e[i].pre) if(e[i].f&&dis[e[i].v]>dis[u]+e[i].w){ dis[e[i].v]=dis[u]+e[i].w; fa[e[i].v]=i; if(!inq[e[i].v]){ inq[e[i].v]=1; q.push(e[i].v); } } } return dis[T]!=inf; } int updata(){ int i=fa[T],x=inf; while(i){ x=min(x,e[i].f); i=fa[e[i^1].v]; } i=fa[T]; while(i){ e[i].f-=x; e[i^1].f+=x; i=fa[e[i^1].v]; } return x*dis[T]; } bool cmp(const Node&x,const Node&y){ if(x.l==y.l) return x.r<y.r; return x.l<y.l; } int main(){ freopen("interv.in","r",stdin); freopen("interv.out","w",stdout); scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r); sort(a+1,a+n+1,cmp); S=0;T=n*2+2;int SS=n*2+1; add(S,SS,k,0); for(int i=1;i<=n;i++){ add(SS,i,inf,0); add(i+n,T,inf,0); add(i,i+n,1,a[i].l-a[i].r); } for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(a[i].r<=a[j].l) add(i+n,j,1,0); int minv=0; while(spfa()) minv+=updata(); printf("%d",-minv); return 0; }
/* 还有一种神奇的做法： 离散化所有区间的端点，把每个端点看做一个顶点，建立附加源S汇T。 建图如下: 从S到顶点1（最左边顶点）连接一条容量为K，费用为0的有向边。 从顶点2N（最右边顶点）到T连接一条容量为K，费用为0的有向边。 从顶点i到顶点i+1(i+1<=2N)，连接一条容量为无穷大，费用为0的有向边。 对于每个区间[a,b]，从a对应的顶点i到b对应的顶点j连接一条容量为1，费用为区间长度的有向边。 */ #include<iostream> #include<cstdio> #include<algorithm> #include<queue> #define N 1010 #define inf 1000000000 using namespace std; int l[N],r[N],len[N],a[N],head[N],dis[N],inq[N],fa[N],n,k,S,T,cnt=1; struct node{int v,f,w,pre;}e[N*100]; queue<int> q; void add(int u,int v,int f,int w){ e[++cnt].v=v;e[cnt].f=f;e[cnt].w=w;e[cnt].pre=head[u];head[u]=cnt; e[++cnt].v=u;e[cnt].f=0;e[cnt].w=-w;e[cnt].pre=head[v];head[v]=cnt; } bool spfa(){ for(int i=0;i<=T;i++) dis[i]=inf; dis[S]=0;q.push(S); while(!q.empty()){ int u=q.front();q.pop();inq[u]=0; for(int i=head[u];i;i=e[i].pre) if(e[i].f&&dis[e[i].v]>dis[u]+e[i].w){ dis[e[i].v]=dis[u]+e[i].w; fa[e[i].v]=i; if(!inq[e[i].v]){ inq[e[i].v]=1; q.push(e[i].v); } } } return dis[T]!=inf; } int updata(){ int i=fa[T],x=inf; while(i){ x=min(x,e[i].f); i=fa[e[i^1].v]; } i=fa[T]; while(i){ e[i].f-=x; e[i^1].f+=x; i=fa[e[i^1].v]; } return x*dis[T]; } int main(){ //freopen("interv.in","r",stdin); //freopen("interv.out","w",stdout); scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d%d",&l[i],&r[i]); a[i*2-1]=l[i];a[i*2]=r[i];len[i]=r[i]-l[i]; } sort(a+1,a+n*2+1); for(int i=1;i<=n;i++){ l[i]=lower_bound(a+1,a+n*2+1,l[i])-a; r[i]=lower_bound(a+1,a+n*2+1,r[i])-a; } S=0;T=n*2+1; add(0,1,k,0);add(n*2,T,k,0); for(int i=1;i<n*2;i++) add(i,i+1,inf,0); for(int i=1;i<=n;i++) add(l[i],r[i],1,-len[i]); int minv=0; while(spfa()) minv+=updata(); printf("%d",-minv); return 0; }