题解 P4066 【[SHOI2003]吃豆豆】 费用流

2018-07-06 19:04:33


前言:

欢迎到博客欣赏

一开始费用流建模比较顺利,到最后发现RE了几个点以为是前向星边开小了,到最后开到MLE也跑不出来。造了个2000个点的数据才发现是SPFA写挂了,然后同样的代码,别人的程序跑4,000,000次循环只用200ms,而我用了50s,卡到90分。。。在检查一下午之后发现是连边的问题,我建的模型有2×2000个点,稠密图下最多可能有8,000,000+(8e6)条边,参考了别人的代码才发现有很多边是不用连的。(连了既增加遍历的时间复杂度,又增加前向星的空间复杂度)2018.7.6目前为止提交记录里有一半都是我交的了

题解:

   这个题和传纸条有点像,不过传纸条是可以交叉,而这个题不能交叉。也就是每一个点只能有一个PACMAN通过,由于这个限制,我们可以联想到网络流的流量上限,豆豆作为费用,跑最大费用最大流。

   如何控制每个点只被一个PACMAN吃掉,是我们要解决的一大问题。我们可以试着把一个点拆成一条边,使得这条边的流量为1,边权为1。也就是当且仅当这条边的两端都在最大流上时,费用才能算上,这就是建模的思路。 也可以当一条边指向一个豆豆时,它的流量是1,不过这样会影响下面的优化,这种做法就是前面90分的做法。

   我们回到题目,题目说PACMAN从原点出发,只能向右或向上,所以当两个点的斜率大于等于零或不存在时$((x1-x2)(y1-y2)\ge 0)$,两个点会连上一条边。如果这样做的话,那么当所有点之间的斜率都大于等于0,就成了一个稠密图,边数超过4e6,双向边加起来就有8e6了,我们就要想办法剪枝(这么多的边SPFA枚举都要花很长时间了),把有些点之间的联系用其他点当桥梁连接起来。

   对于坐标系中一个点,它可以由横坐标非严格小于它,且纵坐标非严格小于它的点(在可行域中)转移。我们为了控制边数,只用连接与它最近的点。我们在可行域中首先找到横坐标最大(同等条件下纵坐标最大)的点,接着屏蔽掉以原点与这个点的连线为对角线的矩形,因为矩形中的点都可以或直接或间接地转移到这个右上角点来

   我们依次这样做下去,就会得到这两个蓝色点和红色点,从蓝点指向红点是一条边权为∞,费用为0的承接边

   不过,在某些情况下,下面剩的两个黑点直接走到红点是更优的解,这样我们只需要把之前拆的点之间重新建一条边,边权为∞,费用为0的承接边,表示不经过这个点的两点连线通过这个点连接到一起,与这个点无关。这样一来,与上面的拆点一起,每个点有了两条自环边,实则分成了两个点,它们之间有两条连线,一条是承接边,一条是费用边,即对费用增加有贡献的边

   我们在这样的图上跑最大费用最大流,最终的流量大多数情况为2,答案为最大费用;当为1时说明一个PACMAN可以解决所有豆豆,此时答案为n。这样一来,所连接的边就约为2×2×2×n即8×n条,双向边最终前向星开100000就足够了。

需要注意一点,我们为了控制只有2个PACMAN,需要从源点1引出一条边指向一个源点2,边权为2,控制最大流不超过2。这样一来,就算有m个PACMAN,也可以通过控制这条边的边权来完成。

Code:

//源点1为0,源点2为4002,汇点为4001,点i的入口为i,出口为2000+i。
#include<cstdio>
#include<cstring>
#include<algorithm>
struct edge
{
    int n,v,w;
    int nxt;
    edge(int n,int v,int w,int nxt)
    {
        this->n=n;
        this->v=v;
        this->w=w;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[405000];
int head[4100],cnt=-1;
void add(int from,int to,int v,int w)
{
    e[++cnt].n=to;
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[from];
    head[from]=cnt;
    e[++cnt].n=from;
    e[cnt].v=0;
    e[cnt].w=-w;
    e[cnt].nxt=head[to];
    head[to]=cnt;
}
struct pnt
{
    int x,y;
    friend bool operator <(pnt a,pnt b)//把点排序
    {
        if(a.x!=b.x)
            return a.x<b.x;
        return a.y<b.y;
    }
}p[2222];
int pre[4222];
int dis[4222];
int q[4000000],l,r;
bool spfa()
{
    bool used[4122];//是否在队列中
    memset(used,0,sizeof(used));
    memset(dis,-0x3f,sizeof(dis));
    l=r=0;
    q[++r]=0;
    dis[0]=0;
    used[0]=true;
    while(l<r)
    {
        int k=q[++l];
        for(int i=head[k];~i;i=e[i].nxt)
        {
            int u=e[i].n;
            if(e[i].v&&dis[u]<dis[k]+e[i].w)
            {
                dis[u]=dis[k]+e[i].w;
                pre[u]=i;
                if(!used[u])
                {
                    used[u]=true;
                    q[++r]=u;
                }
            }
        }
        used[k]=false;
    }
    return dis[4001]>0;
}
int main()
{
    int n;
    scanf("%d",&n);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&p[i].x,&p[i].y);
        add(i,2000+i,1,1);
        add(i,2000+i,2,0);
        add(2000+i,4001,0x3fffffff,0);
        add(4002,i,0x3fffffff,0);
    }
    std::sort(p+1,p+1+n);
    add(0,4002,2,0);
    for(int i=1;i<=n;i++)
    {
        int limy=0;
        for(int j=i-1;j>=1;j--)
        {
            if(p[j].y>p[i].y||p[j].y<limy)
                continue;
            limy=std::max(limy,p[j].y);
            add(2000+j,i,0x3fffffff,0);
        }
    }
    pre[0]=-1;
    int sum=0;
    while(spfa())
    {
        int t=pre[4001];
        sum+=dis[4001];
        while(~t)//增广
        {
            e[t].v--;
            e[t^1].v++;
            t=pre[e[t^1].n];
        }
    }
    printf("%d\n",sum);
    return 0;
}