hdu3572 最大流

Task Schedule

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Appoint description:

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

题意:

有n个任务，m台机器。第i个任务，从si天，到ei天内处理pi遍结束。每次机器只能处理一个任务。

问能否完成所有的任务。

思路:

最大流解决。建立超级源点和汇点。源点和每个任务建边，权值为处理的次数pi，表示完成

该任务需要的ci次数。对于每一个任务，若能在si到ei间，那么从第i个任务建边到si到ei天，

权值为1，表示每一天能够处理一次。从每一天建边到汇点，权值为机器数量，

表示每天能够处理m个任务。如果汇点得到的值等于源点流出的值，那么yes。

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 1<<30
#define MOD 1000000007
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pi acos(-1.0)
using namespace std;
const int MAXN = 1010;
const int MAXM = 200010;
struct node{
    int to;
    int val;
    int next;
}edge[MAXM*2];
int x[MAXN],y[MAXN],z[MAXN];
int pre[MAXN],vis[MAXN],ind,k,n,m,S,T;
void add(int x,int y,int z){
    edge[ind].to = y;
    edge[ind].val = z;
    edge[ind].next = pre[x];
    pre[x] = ind ++;
}
bool bfs(){
    queue<int>q;
    memset(vis,-1,sizeof(vis));
    vis[S] = 0;
    q.push(S);
    while(!q.empty()){
        int tp = q.front();
        q.pop();
        for(int i = pre[tp]; i != -1; i = edge[i].next){
            int t = edge[i].to;
            if(vis[t] == -1 && edge[i].val){
                vis[t] = vis[tp] + 1;
                q.push(t);
            }
        }
    }
    return vis[T] != -1;
}
int dfs(int rt,int low){
    int used = 0;
    if(rt == T){
        return low;
    }
    for(int i = pre[rt]; i != -1 && used < low; i = edge[i].next){
        int t = edge[i].to;
        if(vis[t] == vis[rt] + 1 && edge[i].val){
            int b = dfs(t,min(low-used,edge[i].val));
            edge[i].val -= b;
            edge[i^1].val += b;
            used += b;
        }
    }
    if(used == 0){
        vis[rt] = -1;
    }
    return used;
}
int main(){
    int t,ff = 0;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&m,&k);
        ind = 0;
        memset(pre,-1,sizeof(pre));
        n = 0;
        ll all = 0;
        for(int i = 1; i <= m; i++){
            int fx,fy,fz;
            scanf("%d%d%d",&fx,&fy,&fz);
            x[i] = fy;
            y[i] = fx;
            z[i] = fz;
            n = max(n,z[i]);
            all += y[i];
        }
        for(int i = 1; i <= m; i++){
            for(int j = x[i]; j <= z[i]; j++){
                add(i,j+m,1),add(j+m,i,0);
            }
        }
        S = 0,T = m + n + 1;
        for(int i = 1; i <= m; i++){
            add(S,i,y[i]),add(i,S,0);
        }
        for(int i = 1; i <= n; i++){
            add(i+m,T,k),add(T,i+m,0);
        }
        ll ans = 0;
        while(bfs()){
            while(1){
                ll a = dfs(S,INF);
                if(!a)break;
                ans += a;
            }
        }
        //cout<<S<<" "<<T<<endl;
        printf("Case %d: ",++ff);
        if(ans == all){
            printf("Yes
");
        }
        else {
            printf("No
");
        }
        printf("
");
    }
    return 0;
}