hdu2883

题解：

网络流

用一个离散化

代码:

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int INF=<<;

int si[],ei[],ni[],ti[],head[],h[],num[];

int a[],n,m,sum;

int cnt,ans,c;

struct edge

{

    int x,y,flow,nxt,op;

}em[];

void add(int x,int y,int c)

{

    em[++cnt].x=x;

    em[cnt].y=y;

    em[cnt].flow=c;

    em[cnt].nxt=head[x];

    head[x]=cnt;

    em[cnt].op=cnt+;

    cnt++;

    em[cnt].x=y;

    em[cnt].y=x;

    em[cnt].flow=;

    em[cnt].nxt=head[y];

    head[y]=cnt;

    em[cnt].op=cnt-;

}

int dfs(int x,int flow)

{

    if(x==n+c)

    return flow;

    int temp=flow,pos=n+c+;

    for (int j=head[x];j;j=em[j].nxt)

     {

        int y=em[j].y;

        int w=em[j].flow;

        if (h[x]==h[y]+&&w>)

          {

            int temp_flow=dfs(y,min(temp,w));

            temp-=temp_flow;

            em[j].flow-=temp_flow;

            em[em[j].op].flow+=temp_flow;

            if (!temp||h[]==n+c+)

            return flow-temp;

         }

        if (w>&&h[y]<pos)pos=h[y];

     }

    if (temp==flow)

     {

        num[h[x]]--;

        if (num[h[x]]==)h[]=n+c+;

        else

         {

            h[x]=pos+;

            num[h[x]]++;

         }

     }

    return flow-temp;

}

void isap()

{

     memset(h,,sizeof(h));

     memset(num,,sizeof(num));

     while (h[]<n+c+)ans+=dfs(,INF);

     if (ans==sum)puts("Yes");

     else puts("No");

}

int main()

{

    while (~scanf("%d%d",&n,&m))

     {

        sum=;

        int tot=;

        cnt=;

        memset(head,,sizeof(head));

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

         {

            scanf("%d%d%d%d",si+i,ni+i,ei+i,ti+i);

            a[++tot]=si[i];

            a[++tot]=ei[i];

            add(,i,ni[i]*ti[i]);

            sum+=ni[i]*ti[i];

         }

        sort(a+,a+tot+);

        c=;

        for (int i=;i<=tot;i++)

         if (a[c]!=a[i])a[++c]=a[i];

        for (int i=;i<c;i++)

         {

            int num=(a[i+]-a[i])*m;

            add(n+i,n+c,num);

         }

        for (int i=;i<=c-;i++)

         for (int j=;j<=n;j++)

          if (si[j]<=a[i]&a[i+]<=ei[j])add(j,i+n,INF);

        ans=;

        isap();

     }

    return ;

}