HDU-3572 Task Schedule

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3572

题意：有N个任务，有M个机器。每个任务必须在Si天或者以后开始做，在Ei 天或者之前完成，完成任务必须处理Pi 天。其中，每个任务可以在任意（空闲）机器上做，每个机器同一时刻只能做一个任务，每个任务同一时刻只能被一个机器做，而且任务做到一半可以打断，拿去其他机器做。问：能否在规定时间内把任务做完。

思路：网络流建模，以时间点和每个任务作为节点建模。我们可以选择0为源点（ 因为1<=Pi, Si, Ei），然后源点0与每个任务（每个任务都是一个节点）都连一条容量为Pi的边（令：源点0，任务节点1-N，时间节点N+1-t，汇点t），然后每个任务i都与相应的Si-Ei时间段内的每个时间点连边，边容量为1，这样就保证了每个任务每天只能有一个机器人处理。最后我们要确定汇点，汇点可以取t=Max+N+1(其中Max为结束时间e的最大值，N为任务数），这样确定好汇点之后，再在每个时间点与汇点之间连边，边容量为m（机器数），保证了同一天最多有M个机器处理任务，最后判断sum是否等于满流即可。

//Dinic最大流算法模板
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int Max_v=1100;
struct edge{
    int to,cap,rev;
    edge(int t,int c,int r):to(t),cap(c),rev(r){}
};
int T,N,M;
int level[Max_v];
int iter[Max_v];
vector<edge>G[Max_v];

void add_edge(int from,int to,int cap){
    G[from].push_back(edge(to,cap,G[to].size()));
    G[to].push_back(edge(from,0,G[from].size()-1));
}

void bfs(int s){
    memset(level,-1,sizeof(level));
    queue<int>que;
    que.push(s);level[s]=0;
    while(!que.empty()){
        int v=que.front();que.pop();
        for(int i=0;i<G[v].size();i++){
            edge &e=G[v][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v,int t,int f){
    if(v==t)return f;
    for(int &i=iter[v];i<G[v].size();i++){
        edge &e=G[v][i];
        if(e.cap>0&&level[e.to]>level[v]){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s,int t){
    int flow=0;
    while(true){
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof(iter));
        while(int f=dfs(s,t,inf))flow+=f;
    }
}

int main()
{
    int k=0;
    scanf("%d",&T);
    while(T--){
        int p,s,e,sum=0,Max=0;
        scanf("%d%d",&N,&M);
        for(int i=1;i<=N;i++){
            scanf("%d%d%d",&p,&s,&e);
            sum+=p;
            Max=max(e,Max);
            add_edge(0,i,p); //源点0到第i个任务添加容量为p的边
            for(int v=s;v<=e;v++)add_edge(i,N+v,1); //第i个任务到时间点添加容量为1的边
        }
        int t=N+Max+1;  //计算汇点
        for(int v=N+1;v<t;v++)add_edge(v,t,M); //各时间点到汇点添加容量为M的边

        if(sum==max_flow(0,t))printf("Case %d: Yes\n\n",++k);
        else printf("Case %d: No\n\n",++k);
        for(int i=0;i<=t;i++)G[i].clear();
    }
    return 0;
}