luogu P3358 最长k可重区间集问题

最大费用最大流好题,题目难懂, 构图难想,代码难打!

题目大意:在n个给定的区间中选择若干个区间,其中重合(不包括线段端点——开线段)的次数(不是个数,不然就难了)不能超过k,求这些区间的长度之和的最大值。


方法1:

关于构图:

(网上有一张好图,我就copy吧,但他没有代码)


讲解(我自己补充的):

紫色边,流量为k,因为保证不能超过k;

黑色边,流量为1,好理解,因为选任意一条线段作为起点或终点,有且仅能选一次;

红色边,流量为1,因为任何一条线段有且仅能选一次;

蓝色边(最重要),流量为1,因为你选的线段可能不止一个,所以你可以选与你不相交的线段的起点,且不需要任何代价(因为没有重叠部分)。

这样为什么能求出最优解呢,因为,你每一次从源点如果可以流,就一定会流1的流量到终点,而下一次再流的一定会与这条线短重叠一次,否则就从蓝色边流过去。


关于代码:

#include<cstdio>
#include<queue>
#include<cstring>
#include<queue>
#include<algorithm>
#define INF 2147483647
using namespace std;
queue<int> f;
    int n,k,len=-1,st,ed;
    struct node1{int x,y,c,d,next;} a[100000];
    struct node2{int x,y;} b[50000];
    int last[100000],dis[100000],pre[100000],pos[100000],p[100000];
    bool bz[100000];
bool cmp(node2 x,node2 y)
{
	return x.x<y.x;
}
void ins(int x,int y,int c,int d)
{
    a[++len].x=x;a[len].y=y;a[len].c=c;a[len].d=d;a[len].next=last[x];last[x]=len;
}
bool spfa()
{
    memset(bz,true,sizeof(bz));
    bz[st]=false;
    memset(dis,63,sizeof(dis));
    dis[st]=0;
    p[st]=INF;
    f.push(st);
    while(!f.empty())
    {
        int x=f.front();
        bz[x]=true;
        for(int i=last[x];i>=0;i=a[i].next)
        {
            int y=a[i].y;
            if(a[i].c>0&&dis[y]>dis[x]+a[i].d)
            {
                dis[y]=dis[x]+a[i].d;
                pos[y]=x;
                pre[y]=i;
                p[y]=min(p[x],a[i].c);
                if(bz[y])
                {
                    f.push(y);
                    bz[y]=false;
                }
            }
        }
        f.pop();
    }
    return dis[ed]<1061109567;
}
int flow()
{
    int ans=0;
    while(spfa())
    {
        ans+=p[ed]*dis[ed];
        for(int i=ed;i!=st;i=pos[i])
        {
            a[pre[i]].c-=p[ed];
            a[pre[i]^1].c+=p[ed];
        }
    }
    return ans;
}
int main()
{
	int idx,idy;
	scanf("%d %d",&n,&k);
	st=0,ed=1+n*2+1;
	memset(last,-1,sizeof(last));
	ins(st,st+1,k,0),ins(st+1,st,0,0);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&b[i].x,&b[i].y);
		if(b[i].x>b[i].y) swap(b[i].x,b[i].y);
	}
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		idx=1+i*2-1,idy=1+i*2;
		ins(st+1,idx,1,0),ins(idx,st+1,0,0);
		ins(idy,ed,1,0),ins(ed,idy,0,0);
		ins(idx,idy,1,-(b[i].y-b[i].x)),ins(idy,idx,0,b[i].y-b[i].x);
		for(int j=1;j<i;j++)
			if(b[i].x>=b[j].y) ins(1+j*2,idx,1,0),ins(idx,1+j*2,0,0);
	}
	printf("%d",-flow());
}


方法2:

关于构图:

需要离散化,但效率更优!

(网上有一张好图,我就copy吧)


讲解(我自己补充的):

紫色边,流量为k,好理解,因为保证不能超过k;

黑色边(最重要),流量为INF,因为就像方法1一样,再下一次换边的时候,不需要花费;

红色边,流量为1,因为任何一条线段有且仅能选一次。

这样为什么能求出最优解呢,因为,你每一次从当前点如果可以流,就一定会流1的流量到这条线段的右端点,而下一次再流的一定会与这条线短重叠一次,否则就从红色的边(这样费用更高,就会更优)流过去。

所以,方法1跟方法2的思想一样,但实现方式不同。


关于代码:

#include<cstdio>
#include<queue>
#include<cstring>
#include<queue>
#include<algorithm>
#define INF 2147483647
using namespace std;
queue<int> f;
    int n,k,len=-1,st,ed;
    struct node{int x,y,c,d,next;} a[100000];
    int b[1000][5],list[2000],last[100000],dis[100000],pre[100000],pos[100000],p[100000];
    bool bz[100000];
void ins(int x,int y,int c,int d)
{
    a[++len].x=x;a[len].y=y;a[len].c=c;a[len].d=d;a[len].next=last[x];last[x]=len;
}
bool spfa()
{
    memset(bz,true,sizeof(bz));
    bz[st]=false;
    memset(dis,63,sizeof(dis));
    dis[st]=0;
    p[st]=INF;
    f.push(st);
    while(!f.empty())
    {
        int x=f.front();
        bz[x]=true;
        for(int i=last[x];i>=0;i=a[i].next)
        {
            int y=a[i].y;
            if(a[i].c>0&&dis[y]>dis[x]+a[i].d)
            {
                dis[y]=dis[x]+a[i].d;
                pos[y]=x;
                pre[y]=i;
                p[y]=min(p[x],a[i].c);
                if(bz[y])
                {
                    f.push(y);
                    bz[y]=false;
                }
            }
        }
        f.pop();
    }
    return dis[ed]<1061109567;
}
int flow()
{
    int ans=0;
    while(spfa())
    {
        ans+=p[ed]*dis[ed];
        for(int i=ed;i!=st;i=pos[i])
        {
            a[pre[i]].c-=p[ed];
            a[pre[i]^1].c+=p[ed];
        }
    }
    return ans;
}
int main()
{
	int x,y,t=0,m;
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&b[i][1],&b[i][2]);
		list[++t]=b[i][1],list[++t]=b[i][2];
	}
	sort(list+1,list+t+1);
	m=unique(list+1,list+t+1)-list-1;
	st=0,ed=m+1;
	memset(last,-1,sizeof(last));
	ins(st,1,k,0),ins(1,st,0,0);
	ins(m,ed,k,0),ins(ed,m,0,0);
	for(int i=1;i<m;i++)
		ins(i,i+1,INF,0),ins(i+1,i,0,0);
	for(int i=1;i<=n;i++)
	{
		x=lower_bound(list+1,list+1+m,b[i][1])-list;
		y=lower_bound(list+1,list+1+m,b[i][2])-list;
		ins(x,y,1,-(b[i][2]-b[i][1])),ins(y,x,0,b[i][2]-b[i][1]);
	}
	printf("%d",-flow());
}

版权声明:本文为zsyz_ZZY原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/zsyz_ZZY/article/details/79516521