Task Schedule HDU - 3572

Task Schedule HDU - 3572

题意

有n个项目, m台机器,一台机器同一时间只能完成一个项目, 一个项目可以在多个机器上完成, 给出这n个项目可以开始建设的时间和截止时间及需要多少天完成, 问是否可以在规定时间内完成所有项目

分析

1 建立模型, 用什么方法解决这种问题, 我们看到一天之内最多可以完成m个工作量, 完成一个项目需要的工作量, 这些都可以用流来表示, 于是选择最大流算法
2 建图, 首先确定什么是结点, 什么是边,
(1) 每一天都可以是一个结点, 经过这个节点的最大流量是m,
(2)其次每个任务都可以是一个结点, 这些结点的流量应该等于该任务的完成时间,
(3) 再次, 确定一个源点和汇点
(4) 可以在源点与任务点之间建立边, 边的容量正是完成该任务的时间
(5)在一个任务的开始和截止时间这些天里, 把每一天都与该任务相连,边的容量为1, 表示一天之内一个任务的总时间只能减少1, 不存在同时做一件任务的情况
(6)在每一天与汇点之间建立边, 边的容量是m
3 建图之后套用dinic算法模版(如要详细了解, 刘汝佳算法竞赛训练指南p358)即

参考代码

const int LEN = 1100;
const int maxn = 1e8;
struct Edge{
  int from,to,cap,flow;
  Edge(int u,int v,int w,int f): from(u),to(v),cap(w),flow(f){}
};
struct Dinic{
   int n,m,s,t;
   vector<Edge> edges;//存边
   vector<int> G[LEN];//结点
   int vis[LEN];//bfs需要标记是否访问过该点
   int d[LEN];//表示源点到该点的层次
   int cur[LEN];//代表dfs已经搜到了那个点
   void init(int n)//初始化
   {
       this->n  = n;
       for(int i = 0;i < n; ++i)
        G[i].clear();
       edges.clear();
   }
   void Add(int u,int v,int w)//添加边
   {
       edges.push_back(Edge(u,v,w,0));
       edges.push_back(Edge(v,u,0,0));
       m = edges.size();
       G[u].push_back(m-2);
       G[v].push_back(m-1);
   }
   bool Bfs(void)//分层
   {
      me(d);
      me(vis);
      d[s] = 0;
      vis[s] = 1;

      queue<int> Q;//队列进行广搜
      Q.push(s);
      while(!Q.empty())
      {
          int q = Q.front();Q.pop();

          for(size_t i = 0;i < G[q].size();++i)
          {
              Edge &tmp = edges[G[q][i]];
              if(!vis[tmp.to]&&tmp.cap>tmp.flow)
              {
                  vis[tmp.to] = 1;
                  d[tmp.to] = d[q] + 1;//结点层次是上一次的加一
                  Q.push(tmp.to);
              }
          }
      }
      return vis[t];
   }
   int Dfs(int node,int a)
   {

       if(node == t||a == 0)//如果搜到了汇点或者分配到当前节点的流量为零, 返回
        return a;
       int flow =  0,f;
       for(int &i = cur[node];i < G[node].size();++i)//注意用的是引用
       {
          Edge &tmp = edges[G[node][i]];//同样也是引用
          if(d[tmp.to]==d[node]+1&&(f = Dfs(tmp.to,min(a,tmp.cap-tmp.flow)))>0)
          {
              flow += f;
              tmp.flow += f;
              edges[G[node][i]^1].flow -= f;//修改路径
              a -= f;
              if(a==0)
                break;
          }
       }
       return flow;
   }
   int MaxFlow(int s,int t)
   {
       this->s = s;
       this->t = t;
       int flow = 0;
       while(Bfs())
       {
           me(cur);
           flow += Dfs(s,maxn);
       }
       return flow;

   }


};
Dinic dinic;

int p[LEN];
int e[LEN];
int s[LEN];
int main()
{
    int N,M,S,T;
    int t,kase = 0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&N,&M);
        S = 0, T = 1000;//源点设为零, 汇点设为一千
        dinic.init(1000+10);
// int u,v,w;
        int sum = 0;
        for(int i = 0;i < N;++i)
        {
            scanf("%d %d %d",&p[i],&s[i],&e[i]);
            sum += p[i];
        }
        for(int i = 1;i <= 500; ++i)
        {
            dinic.Add(i,T,M);//在每一天到汇点之间建立边
        }
        for(int i = 0;i < N; ++i)
        {
            dinic.Add(S,501+i,p[i]);//在源点到各个人物之间建立边
            for(int j = s[i];j <= e[i];++j)
            {
                dinic.Add(501+i,j,1);//在各任务时间内每一天与与该任务建立边
            }
        }
        int ans = 0;
        ans = dinic.MaxFlow(S,T);
        if(ans == sum)
            printf("Case %d: Yes\n",++kase);
        else
            printf("Case %d: No\n",++kase);
// if(t)
         printf("\n");

    }



    return 0;
}