Task Schedule(HDOJ 3572)

文章目录[x]
  1. 1:Problem Description
  2. 2:Input
  3. 3:Output
  4. 4:Sample Input
  5. 5:Sample Output
  6. 6:My Code

Problem Description

Our geometry princess XMM has stoped her study in computational geometry to concentrate on her newly opened factory. Her factory has introduced M new machines in order to process the coming N tasks. For the i-th task, the factory has to start processing it at or after day Si, process it for Pi days, and finish the task before or at day Ei. A machine can only work on one task at a time, and each task can be processed by at most one machine at a time. However, a task can be interrupted and processed on different machines on different days.
Now she wonders whether he has a feasible schedule to finish all the tasks in time. She turns to you for help. 

Input

On the first line comes an integer T(T<=20), indicating the number of test cases.

You are given two integer N(N<=500) and M(M<=200) on the first line of each test case. Then on each of next N lines are three integers Pi, Si and Ei (1<=Pi, Si, Ei<=500), which have the meaning described in the description. It is guaranteed that in a feasible schedule every task that can be finished will be done before or at its end day.

Output

For each test case, print “Case x: ” first, where x is the case number. If there exists a feasible schedule to finish all the tasks, print “Yes”, otherwise print “No”.

Print a blank line after each test case. 

Sample Input

2
4 3
1 3 5 
1 1 4
2 3 7
3 5 9

2 2
2 1 3
1 2 2

Sample Output

Case 1: Yes
   
Case 2: Yes

My Code

有n个任务和m台机器,每个任务可以在第si到第ei天内任选pi天完成。

(1)每天只能同时做m个任务,因为只有m台机器,每台机器只能同时做一个任务。

(2)每个任务同时只能有由一个机器做,所以每个任务需要做pi天

首先建立一个超级源点,然后和每个任务连起来,容量为pi,如果这n个弧都满流就说明,所有任务都完成了。

每个任务和si到ei的每一天连起来,容量为1,因为第(2)条

最后每一天都和超级汇点连起来,容量为m,因为第(1)条

剩下的就跑最大流了,如果最大流等于∑pi,就说明任务完成了

#include <iostream>
#include <cstring>
#include <queue>
#define maxn 1005
#define maxm 250005
#define inf 0x3f3f3f3f
using namespace std;
int T;
int n, m;
struct edge
{
      int v;
      int c;
      int next;
} e[maxm << 1];
int tot;
int cnt;
int head[maxn];
int cur[maxn];
void add(int u, int v, int c)
{
      e[++tot].v = v;
      e[tot].c = c;
      e[tot].next = head[u];
      head[u] = tot;
}
int dep[maxn];
bool bfs(int s, int t)
{
      queue<int> q;
      memset(dep, 0, sizeof(dep));
      dep[s] = 1;
      q.push(s);
      for (int i = 0; i <= t; i++) //总的点数不是n,而是t+1
            cur[i] = head[i];
      while (!q.empty())
      {
            s = q.front();
            q.pop();
            for (int i = head[s]; ~i; i = e[i].next)
                  if (e[i].c && !dep[e[i].v])
                  {
                        dep[e[i].v] = dep[s] + 1;
                        if (e[i].v == t)
                              return true;
                        q.push(e[i].v);
                  }
      }
      return false;
}
int dfs(int s, int t, int flow)
{
      if (s == t || !flow)
            return flow;
      int ans = 0;
      for (int &i = cur[s]; ~i; i = e[i].next)
            if (e[i].c && dep[e[i].v] == dep[s] + 1)
            {
                  int res = dfs(e[i].v, t, min(flow, e[i].c));
                  if (!res)
                        dep[e[i].v] = 0;
                  e[i].c -= res;
                  e[i ^ 1].c += res;
                  ans += res;
                  flow -= res;
                  if (!flow)
                        break;
            }
      return ans;
}
void init()
{
      memset(e, -1, sizeof(e));
      memset(head, -1, sizeof(head));
      tot = -1;
}
int dinic(int s, int t)
{
      int ans = 0;
      while (bfs(s, t))
            ans += dfs(s, t, inf);
      return ans;
}
int main()
{
      cin >> T;
      while (T--)
      {
            init();
            cin >> n >> m;
            int sum = 0;
            int maxd = 0;
            int s = 0;
            for (int i = 1; i <= n; i++)
            {
                  int pi, si, ei;
                  cin >> pi >> si >> ei;
                  sum += pi;            //记录源点流出的最大流量,即每个任务完成所需时间的累加
                  maxd = max(ei, maxd); //记录最晚的那一天
                  add(s, i, pi);        //超级源点到每个任务的流量为任务所需时间pi
                  add(i, s, 0);         //反悔边
                  for (int j = si; j <= ei; j++)
                  {
                        add(i, j + n, 1); //每个任务和其开始到结束的每一天连起来,容量为1
                        add(j + n, i, 0); //因为做一天只能算一天的任务,不能一天把pi天的都做完
                  }
            }
            int t = maxd + n + 1; //超级汇点
            for (int i = n + 1; i < t; i++)
            {
                  add(i, t, m); //每一天到汇点的容量为m
                  add(t, i, 0); //因为每天只能同时有m个机器工作
            }
            if (dinic(s, t) == sum) //如果每个任务都干满了pi天,那就说明完成了
                  cout << "Case " << ++cnt << ": Yes" << endl;
            else
                  cout << "Case " << ++cnt << ": No" << endl;
            if (t)
                  cout << endl;
      }
      return 0;
}
点赞
Title - Artist
0:00