hdu2883

题解：

网络流

用一个离散化

代码:

#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
const int INF=1<<30;  
int si[210],ei[210],ni[210],ti[210],head[2100],h[2100],num[4200];  
int a[410],n,m,sum;  
int cnt,ans,c;  
struct edge  
{  
    int x,y,flow,nxt,op;  
}em[1000010];  
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+1;
    cnt++;  
    em[cnt].x=y;  
    em[cnt].y=x;  
    em[cnt].flow=0;  
    em[cnt].nxt=head[y];  
    head[y]=cnt;  
    em[cnt].op=cnt-1;  
}  
int dfs(int x,int flow)  
{  
    if(x==n+c)  
    return flow;  
    int temp=flow,pos=n+c+1;  
    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]+1&&w>0)  
          {  
            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[0]==n+c+1)  
            return flow-temp;  
         }  
        if (w>0&&h[y]<pos)pos=h[y];  
     }  
    if (temp==flow)  
     {   
        num[h[x]]--;  
        if (num[h[x]]==0)h[0]=n+c+1;  
        else  
         {  
            h[x]=pos+1;  
            num[h[x]]++;  
         }  
     }  
    return flow-temp;  
}  
void isap()  
{  
     memset(h,0,sizeof(h));  
     memset(num,0,sizeof(num));  
     while (h[0]<n+c+1)ans+=dfs(0,INF);    
     if (ans==sum)puts("Yes");  
     else puts("No");  
}  
int main()  
{  
    while (~scanf("%d%d",&n,&m))  
     {  
        sum=0;  
        int tot=0;  
        cnt=0;  
        memset(head,0,sizeof(head));  
        for (int i=1;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(0,i,ni[i]*ti[i]);  
            sum+=ni[i]*ti[i];  
         }  
        sort(a+1,a+tot+1);  
        c=0;  
        for (int i=1;i<=tot;i++)  
         if (a[c]!=a[i])a[++c]=a[i];    
        for (int i=1;i<c;i++)  
         {  
            int num=(a[i+1]-a[i])*m;  
            add(n+i,n+c,num);  
         }  
        for (int i=1;i<=c-1;i++)  
         for (int j=1;j<=n;j++)  
          if (si[j]<=a[i]&a[i+1]<=ei[j])add(j,i+n,INF);    
        ans=0;  
        isap();  
     }      
    return 0;  
}