【网络流24题】No.21 （最长 k 可重区间集问题最长不相交路径最大费用流）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

【】

输入文件示例
input.txt
4 2
1 7
6 8
7 10
9 13
输出文件示例
output.txt
15

【分析】

直接co题解好了，写得挺全。。

【建模方法】
方法1
按左端点排序所有区间，把每个区间拆分看做两个顶点<i.a><i.b>，建立附加源S汇T，以及附加顶点S’。
1、连接S到S’一条容量为K，费用为0的有向边。
2、从S’到每个<i.a>连接一条容量为1，费用为0的有向边。
3、从每个<i.b>到T连接一条容量为1，费用为0的有向边。
4、从每个顶点<i.a>到<i.b>连接一条容量为1，费用为区间长度的有向边。
5、对于每个区间i，与它右边的不相交的所有区间j各连一条容量为1，费用为0的有向边。
求最大费用最大流，最大费用流值就是最长k可重区间集的长度。
方法2
离散化所有区间的端点，把每个端点看做一个顶点，建立附加源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，费用为区间长度的有向边。
求最大费用最大流，最大费用流值就是最长k可重区间集的长度。
【建模分析】
这个问题可以看做是求K条权之和最大的不想交路径，每条路径为一些不相交的区间序列。由于是最大费用流，两条路径之间一定有一些区间相交，可以看做事相交部分重复了2次，而K条路经就是最多重复了K次。最简单的想法就是把区间排序后，不相交的区间之间连接一条边，由于每个区间只能用一次，所以要拆点，点内限制流量。如果我们改变一下思路，把端点作为网络中的顶点，区间恰恰是特定一些端点之间的边，这样建模的复杂度更小。方法1的边数是O(N^2)的，而方法2的边数是O(N)的，可以解决更大规模的问题。

感觉我的数据错了hhh

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define Maxn 101000
#define INF 0xfffffff struct node
{
int x,y,f,o,c,next;
}t[Maxn*];int len;
int first[Maxn]; int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;} void ins(int x,int y,int f,int c)
{
t[++len].x=x;t[len].y=y;t[len].f=f;t[len].c=c;
t[len].next=first[x];first[x]=len;t[len].o=len+;
t[++len].x=y;t[len].y=x;t[len].f=;t[len].c=-c;
t[len].next=first[y];first[y]=len;t[len].o=len-;
} int st,ed;
queue<int > q;
int dis[Maxn],pre[Maxn],flow[Maxn];
bool inq[Maxn];
bool bfs()
{
while(!q.empty()) q.pop();
// memset(dis,-1,sizeof(dis));
for(int i=;i<=ed;i++) dis[i]=-INF;
memset(inq,,sizeof(inq));
q.push(st);dis[st]=;flow[st]=INF;inq[st]=;
while(!q.empty())
{
int x=q.front();
for(int i=first[x];i;i=t[i].next) if(t[i].f>)
{
int y=t[i].y;
if(dis[y]<dis[x]+t[i].c)
{
dis[y]=dis[x]+t[i].c;
pre[y]=i;
flow[y]=mymin(flow[x],t[i].f);
if(!inq[y])
{
inq[y]=;
q.push(y);
}
}
}
inq[x]=;q.pop();
}
if(dis[ed]>-INF) return ;
return ;
} void output()
{
for(int i=;i<=len;i+=)
printf("%d->%d %d %d\n",t[i].x,t[i].y,t[i].f,t[i].c);
printf("\n");
} int max_flow()
{
int ans=,sum=;
while(bfs())
{
sum+=dis[ed]*flow[ed];
ans+=flow[ed];
int now=ed;
while(now!=st)
{
t[pre[now]].f-=flow[ed];
t[t[pre[now]].o].f+=flow[ed];
now=t[pre[now]].x;
}
}
return sum;
} struct hp
{
int x,id;
}tt[Maxn];int tl=;
int nx[Maxn],ny[Maxn],ln[Maxn]; bool cmp(hp x,hp y) {return x.x<y.x;} void init()
{
int n,k;
scanf("%d%d",&n,&k);
len=;
memset(first,,sizeof(first));
int mx=;
for(int i=;i<=n;i++)
{
int x,y;
// scanf("%d%d",&x,&y);
// ins(x,y,1,y-x);
scanf("%d%d",&nx[i],&ny[i]);
ln[i]=ny[i]-nx[i];
tt[++tl].x=nx[i];tt[tl].id=i;
tt[++tl].x=ny[i];tt[tl].id=i+n;
// mx=mymax(mx,y);
}
sort(tt+,tt++tl,cmp);
int pp=;
int now=tt[].x;tt[].x=;
for(int i=;i<=tl;i++)
{
if(tt[i].x!=now) pp++,now=tt[i].x;
tt[i].x=pp;
}
for(int i=;i<=tl;i++)
{
if(tt[i].id>n) ny[tt[i].id-n]=tt[i].x;
else nx[tt[i].id]=tt[i].x;
}
for(int i=;i<=n;i++) ins(nx[i],ny[i],,ln[i]);
mx=pp;
st=mx+;ed=st+;
ins(st,,k,);
for(int i=;i<mx;i++) ins(i,i+,k,);
ins(mx,ed,k,);
} int main()
{
init();
// output();
int ans;
ans=max_flow();
printf("%d\n",ans);
return ;
}