hdu 3572 Task Schedule

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

题目大意：给出任务数量，和机器数量。每个任务包括三个信息：一台机器需要处理的时间，起始时间，终止时间。问能否在每个任务的时限内完成所有人物。

解题思路：完全没思路，觉得这应该是贪心的题目。后来去看了题解……。设置一个超级源点，连向所有的任务，容量为该任务需要处理的时间。然后每个任务连向他们对应的时间，例如一个任务时限从2到4，则该任务结点，连向2 3 4的时间节点，容量为1。然后所有的时间节点，连向超级汇点，容量为机器数量。挺巧妙的，但我想不到……

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; const int INF = 0x3f3f3f3f; const int N = 2500; const int M = 400005; const int FIN = 2015; typedef long long ll; int n, m, s, t, sum; int ec, head[N], first[N], que[N], lev[N]; int Next[M], to[M], v[M]; void init() { sum = 0; ec = 0; memset(first, -1, sizeof(first)); s = 0, t = FIN; } void addEdge(int a,int b,int c) { to[ec] = b; v[ec] = c; Next[ec] = first[a]; first[a] = ec++; to[ec] = a; v[ec] = 0; Next[ec] = first[b]; first[b] = ec++; } int BFS() { int kid, now, f = 0, r = 1, i; memset(lev, 0, sizeof(lev)); que[0] = s, lev[s] = 1; while (f < r) { now = que[f++]; for (i = first[now]; i != -1; i = Next[i]) { kid = to[i]; if (!lev[kid] && v[i]) { lev[kid] = lev[now] + 1; if (kid == t) return 1; que[r++] = kid; } } } return 0; } int DFS(int now, int sum) { int kid, flow, rt = 0; if (now == t) return sum; for (int i = head[now]; i != -1 && rt < sum; i = Next[i]) { head[now] = i; kid = to[i]; if (lev[kid] == lev[now] + 1 && v[i]) { flow = DFS(kid, min(sum - rt, v[i])); if (flow) { v[i] -= flow; v[i^1] += flow; rt += flow; } else lev[kid] = -1; } } return rt; } int dinic() { int ans = 0; while (BFS()) { for (int i = 0; i <= t; i++) { head[i] = first[i]; } ans += DFS(s, INF); } return ans; } void input() { int Min = INF, Max = 0; scanf(%d %d, &n, &m); int a, b, c; for (int i = 1; i <= n; i++) { scanf(%d %d %d, &a, &b, &c); sum += a; addEdge(s, i, a); for (int j = b; j <= c; j++) { addEdge(i, j + n, 1); } if (c < b) swap(c, b); if (Min > b) Min = b; if (Max < c) Max = c; } for (int i = Min; i <= Max; i++) { addEdge(i + n, t, m); } } int main() { int T, Case = 1; scanf(%d, &T); while (T--) { printf(Case %d: , Case++); init(); input(); if (dinic() == sum) printf(Yes ); else printf(No ); puts(); } return 0; } 
       
      
     
    
   

?