题解 P4066 【[SHOI2003]吃豆豆】

· · 题解

题目有以下要求：

1：一个豆子只能吃一次（废话）

2：只能吃右上角的豆子

3：两条路径不交叉

首先第3个要求并没有什么用，因为交叉路径可以转换为不交叉路径，这种思路存在于这道题 （普及-），即对调交叉点之后的路径

所以题目变成了求两条路径使得吃到的豆子最多，通过思考得出可以用费用流来做

先考虑建图

1.首先s连0号点，容量为2，表示只有两条路径

2.点与点之间，我们很容易想到，如果j在i的右上角，那么i连向j，容量为2

3.每个点连t，表示都可以作为结束点

但是有个问题，费用怎么得到？

由于一个豆子只能被吃一次，所以在之前的边上直接加费用1是不正确的。我们可以将一个点x拆成x1和x2，x的入边连给x1，出边连给x2，x1和x2之间连两条容量为1的边，费用分别为0和1，即可实现每个点只被统计一次

解决了建图问题之后，跑最大费用最大流即可

看起来好像是这样的

但是点与点之间可能有很多边，比如点（x,y）依次递增，最大就有n^2条边。通过观察可以发现，有些边是没有必要的，比如x->y,x->z,y->z这三条边中，x->z就没有意义，x，z之间可以间接连接，于是便有了下面这个连边方法

先将所有点按x升序排列，for(1~n)，对于一个点i，如果它连向了后面的某个点j，那么对于（j+1~n）中的点，如果它的纵坐标大于j，就没有必要直接连接它，因为之后j会连接它，i可以间接连接。也就是说，从i出发直接相连的点，它们的纵坐标一定是降序排列的

Q：如果像上面那样做，万一i后面的点全是降序呢，那还不是要炸

A：由i出发的直接相连的边确实变成了很多条，但是对于i+1，之后的所有点的纵坐标都比它小，就不会产生连边了，所以这种情况平均下来边还是比较少

Code：

#include<bits/stdc++.h>
#define N 6010
#define INF 100000005
using namespace std;
int n,m,s,t,num;
int dis[N],flow[N],preedge[N],pre[N];
int maxflow,maxcost;
bool exist[N];
struct Node {int x,y;} node[N];

struct Edge
{
    int next,to,flow,dis;
}edge[N*100];int head[N],cnt=1;
void add_edge(int from,int to,int flow,int dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].flow=flow;
    edge[cnt].dis=dis;
    head[from]=cnt;
}
void ad(int from,int to,int flow,int dis)
{
    add_edge(from,to,flow,dis);
    add_edge(to,from,0,-dis);
}

template <class T>
void read(T &x)
{
    char c;int sign=1;
    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
    while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign; 
}
bool Spfa(int s,int t)
{
    memset(dis,-100,sizeof(dis));
    memset(flow,100,sizeof(flow));
    memset(exist,0,sizeof(exist));
    queue<int> q;
    pre[t]=-1; exist[s]=1; dis[s]=0; q.push(s);
    while(!q.empty())
    { 
        int u=q.front();q.pop();exist[u]=0;
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(edge[i].flow>0&&dis[v]<dis[u]+edge[i].dis)
            {
                dis[v]=dis[u]+edge[i].dis;
                flow[v]=min(edge[i].flow,flow[u]);
                pre[v]=u;
                preedge[v]=i;
                if(!exist[v])
                {
                    exist[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return pre[t]!=-1;
}
void MCMF()
{
    while(Spfa(s,t))
    {
        maxflow+=flow[t];
        maxcost+=flow[t]*dis[t];
        int now=t;
        while(now!=s)
        {
            edge[preedge[now]].flow-=flow[t];
            edge[preedge[now]^1].flow+=flow[t];
            now=pre[now];
        }
    }
}
bool cmp(Node a,Node b) {return a.x!=b.x ? a.x<b.x : a.y<b.y;}
int main()
{
    read(n);
    s=n+1;t=n+2;m=n*2;
    node[0].x=node[0].y=0;
    for(int i=1;i<=n;++i) read(node[i].x),read(node[i].y);
    sort(node+1,node+n+1,cmp);//按x排序 
    for(int i=0;i<=n;++i)
    {
        int minn=0;
        for(int j=i+1;j<=n;++j)//保证xj>=xi 
        {
            if(node[j].y<node[i].y) continue;//无法到达 
            if((!minn)||node[j].y<minn)//更低则必须加边 
            {
                minn=node[j].y;
                ad(i+m,j,2,0);
            }
        }
    }
    ad(s,0,2,0);
    ad(0,m,2,0);
    for(int i=1;i<=n;++i) ad(i,i+m,1,1),ad(i,i+m,1,0),ad(i+m,t,2,0);
    MCMF();
    cout<<maxcost<<endl;
    return 0;
}