hdu 3572 Task Schedule（最大流）

hdu 3572 Task Schedule（最大流）

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;
}