洛谷P4066/bzoj1930 [SHOI2003]吃豆豆 题解【费用流】【最短路】

点击量：278

   我估计现在为止洛谷上提交记录有一半都是我的。。。

目录

题目描述

两个PACMAN吃豆豆。一开始的时候，PACMAN都在坐标原点的左下方，豆豆都在右上方。PACMAN走到豆豆处就会吃掉它。PACMAN行走的路线很奇怪，只能向右走或者向上走，他们行走的路线不可以相交。 请你帮这两个PACMAN计算一下，他们俩加起来最多能吃掉多少豆豆。

输入输出格式

输入格式：

第一行为一个整数N，表示豆豆的数目。 接下来 N 行，每行一对正整数，表示第i个豆豆的坐标。任意两个豆豆的坐标都不会重合。

输出格式：

仅有一行包含一个整数，即两个PACMAN加起来最多能吃掉的豆豆数量

输入输出样例

输入样例#1：

8

8 1

1 5

5 7

2 2

7 8

4 6

3 3

6 4

输出样例#1：

7

说明

N<=2000

样例说明

 

前言：

   一开始费用流建模比较顺利，到最后发现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;
}