743. [网络流24题] 最长k可重区间集
★★★ 输入文件：interv.in 输出文件：interv.out 简单对比
时间限制：1 s 内存限制：128 MB
- «问题描述：
- «编程任务：
- 对于给定的开区间集合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
这样的区间建图比较好想，因为以前做过用最短路的最小区间覆盖问题，想法类似
BYVOID：
离散化所有区间的端点，把每个端点看做一个顶点，建立附加源S汇T。
1、从S到顶点1（最左边顶点）连接一条容量为K，费用为0的有向边。
2、从顶点2N（最右边顶点）到T连接一条容量为K，费用为0的有向边。
3、从顶点i到顶点i+1(i+1<=2N)，连接一条容量为无穷大，费用为0的有向边。
4、对于每个区间[a,b]，从a对应的顶点i到b对应的顶点j连接一条容量为1，费用为区间长度的有向边。
两点：
1.相邻的连一条边，避免了每个点都和s t连边
2.容量限制为k，经过每个点的边数一定<=k
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=,M=1e5+,INF=1e9;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
}
int n,k,mp[N],m,l[N],r[N],s,t;
int Bin(int v){
int l=,r=m;
while(l<=r){
int mid=(l+r)>>;
if(mp[mid]==v) return mid;
if(v<mp[mid]) r=mid-;
else l=mid+;
}
return -;
}
struct edge{
int v,ne,c,f,w;
}e[M<<];
int cnt,h[N];
inline void ins(int u,int v,int c,int w){
//printf("ins %d %d %d %d %d %d\n",u,v,c,w,mp[u],mp[v]);
cnt++;
e[cnt].v=v;e[cnt].c=c;e[cnt].f=;e[cnt].w=w;
e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].c=;e[cnt].f=;e[cnt].w=-w;
e[cnt].ne=h[v];h[v]=cnt;
}
void build(){
s=;t=m+;
ins(s,,k,);ins(m,t,k,);
for(int i=;i<m;i++)
ins(i,i+,INF,);
for(int i=;i<=n;i++)
ins(Bin(l[i]),Bin(r[i]),,-(r[i]-l[i]));
}
int q[N],head,tail,d[N],inq[N],pre[N],pos[N];
inline void lop(int &x){if(x==N) x=;else if(x==) x=N-;}
bool spfa(){
memset(d,,sizeof(d));
memset(inq,,sizeof(inq));
head=tail=;
q[tail++]=s;inq[s]=;d[s]=;
pre[t]=-;
while(head!=tail){
int u=q[head++];inq[u]=;lop(head);
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v,w=e[i].w;
if(e[i].c>e[i].f&&d[v]>d[u]+w){
d[v]=d[u]+w;
pos[v]=i;pre[v]=u;
if(!inq[v]){
inq[v]=;
if(d[v]<d[q[head]]) head--,lop(head),q[head]=v;
else q[tail++]=v,lop(tail);
}
}
}
}
return pre[t]!=-;
}
int mcmf(){
int flow=,cost=;
while(spfa()){
int f=INF;
for(int i=t;i!=s;i=pre[i]) f=min(f,e[pos[i]].c-e[pos[i]].f);
flow+=f;cost+=-d[t]*f;//printf("flow %d\n",flow);
for(int i=t;i!=s;i=pre[i]){
int p=pos[i];
e[p].f+=f;
e[((p-)^)+].f-=f;
}
}
return cost;
}
int main(){
freopen("interv.in","r",stdin);
freopen("interv.out","w",stdout);
n=read();k=read();
for(int i=;i<=n;i++) mp[++m]=l[i]=read(),mp[++m]=r[i]=read();
sort(mp+,mp++m);
int p=;mp[++p]=mp[];
for(int i=;i<=m;i++) if(mp[i]!=mp[i-]) mp[++p]=mp[i];
m=p;
build();
printf("%d\n",mcmf());
}