hdu2883 最大流，判断满流 优化的SAP算法

　　这是09年的多校联赛题目，比10年的难度要大。如果没做过hdu3572，建议先去做。有了解题思维再来做这题。

　　这题与hdu3572类似。但是1 <= si < ei <= 1,000,000的限制使得我们如果像HDU3572那样建图，会使得边的数量太多。从而超时。

　　看看别人的题解 http://www.cnblogs.com/wally/archive/2013/05/03/3057066.html  离散化的思想

　

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=,M=, INF=0x3f3f3f3f;

struct node

{

    int to,next,w;

}edge[M];

int head[N],numh[N],h[N],cure[N],pre[N];

//numh:GAP优化的统计高度数量数组; h：距离标号数组; cure:当前弧

int ans,tot;

void SAP(int s, int e,int n)

{

    int flow,u,tmp,neck,i;

    ans=;

    for(i=;i<=n;i++)

        cure[i]=head[i];

    numh[]=n;

    u=s;

    while(h[s]<n)

    {

        if(u==e)

        {

            flow =INF;

            for(i=s;i!=e;i=edge[cure[i]].to)

            {

                if(flow>edge[cure[i]].w)

                {

                    neck=i;

                    flow =edge[cure[i]].w;

                }

            }

            for(i=s;i!=e;i=edge[cure[i]].to)

            {

                tmp=cure[i];

                edge[tmp].w-=flow;

                edge[tmp^].w+=flow;

            }

            ans+=flow;

            u=neck;

        }

        for(i=cure[u];i!=-;i=edge[i].next)

            if(edge[i].w && h[u]==h[edge[i].to]+) break;

        if(i!=-) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;}

        else

        {

            if(==--numh[h[u]]) break; //GAP优化

            cure[u]=head[u];

            for(tmp=n,i=head[u];i!=-;i=edge[i].next)

                if(edge[i].w) tmp=min(tmp, h[edge[i].to]);

            h[u]=tmp+;

            ++numh[h[u]];

            if(u!=s) u=pre[u];

        }

    }

}

void init()

{

    tot=;

    memset(head,-,sizeof(head));

    memset(pre,-,sizeof(pre));

    memset(h,,sizeof(h));

    memset(numh,,sizeof(numh));

}

void addedge(int i,int j,int w)

{

    edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++;

    edge[tot].to=i;edge[tot].w=;edge[tot].next=head[j];head[j]=tot++;

}

int T[N],st[N],ed[N];

int main()

{

    //freopen("test.txt","r",stdin);

    int n,m,i,j,k,a,b,c,sum,s,t;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        init();

        sum=;s=n+;

        k=;

        for(i=;i<=n;i++)

        {

            scanf("%d%d%d%d",&st[i],&b,&ed[i],&t);

            sum+=b*t;

            addedge(s,i,b*t);

            T[k++]=st[i];

            T[k++]=ed[i];

        }

        sort(T,T+k);

        j=;

        for(i=;i<k;i++)

            if(T[j]!=T[i]) T[++j]=T[i];

        k=s++j;

        for(i=;i<=j;i++)

        {

            addedge(s+i,k,m*(T[i]-T[i-]));

            for(t=;t<=n;t++)

                if(st[t]<=T[i-]&&ed[t]>=T[i]) addedge(t,i+s,INF);

        }

        SAP(s,k,k);

        if(ans==sum) printf("Yes\n");

        else printf("No\n");

    }

    return ;

}