最大流任务调度+离散化——hdu2883

思想就是把时间段离散化，然后用个点来表示一段时间

#include<iostream>

#include<cstdio>

#include<cstring>

#include <algorithm>

#include <math.h>

#include <queue>

using namespace std;

const int N = ;

const int INF = ;

struct Edge{

    int v,w,next;

}edge[N*N];

int head[N];

int level[N];

int tot;

void init()

{

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

    tot=;

}

void addEdge(int u,int v,int w,int &k)

{

    edge[k].v = v,edge[k].w=w,edge[k].next=head[u],head[u]=k++;

    edge[k].v = u,edge[k].w=,edge[k].next=head[v],head[v]=k++;

}

int BFS(int src,int des)

{

    queue<int>q;

    memset(level,,sizeof(level));

    level[src]=;

    q.push(src);

    while(!q.empty())

    {

        int u = q.front();

        q.pop();

        if(u==des) return ;

        for(int k = head[u]; k!=-; k=edge[k].next)

        {

            int v = edge[k].v;

            int w = edge[k].w;

            if(level[v]==&&w!=)

            {

                level[v]=level[u]+;

                q.push(v);

            }

        }

    }

    return -;

}

int dfs(int u,int des,int increaseRoad){

    if(u==des||increaseRoad==) return increaseRoad;

    int ret=;

    for(int k=head[u];k!=-;k=edge[k].next){

        int v = edge[k].v,w=edge[k].w;

        if(level[v]==level[u]+&&w!=){

            int MIN = min(increaseRoad-ret,w);

            w = dfs(v,des,MIN);

            if(w > )

            {

                edge[k].w -=w;

                edge[k^].w+=w;

                ret+=w;

                if(ret==increaseRoad) return ret;

            }

            else level[v] = -;

            if(increaseRoad==) break;

        }

    }

    if(ret==) level[u]=-;

    return ret;

}

int Dinic(int src,int des)

{

    int ans = ;

    while(BFS(src,des)!=-) ans+=dfs(src,des,INF);

    return ans;

}

int n,m;

int s[N],num[N],e[N],t[N];

int time[N];

int main()

{

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

        init();

        int k = ;

        int sum = ;

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

            scanf("%d%d%d%d",&s[i],&num[i],&e[i],&t[i]);

            sum += num[i]*t[i];

            time[++k] = s[i];

            time[++k] = e[i];

        }

        sort(time+,time+k+);

        int cnt = ;

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

            if(time[i]==time[i-]) continue;

            time[++cnt] = time[i];

        }

        int src = ,des = n+cnt+;

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

            addEdge(src,i,num[i]*t[i],tot);

        }

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

            for(int j=;j<=cnt;j++){

                if(s[i]<=time[j-]&&time[j]<=e[i]){

                    addEdge(i,n+j,INF,tot);

                }

            }

        }

        for(int i=;i<=cnt;i++){

            addEdge(n+i,des,(time[i]-time[i-])*m,tot);

        }

        if(Dinic(src,des)==sum) printf("Yes\n");

        else printf("No\n");

    }

    return ;

}