Task Schedule

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5007 Accepted Submission(s): 1636


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

Author allenlowesy
Source 2010 ACM-ICPC Multi-University Training Contest（13）——Host by UESTC

題意：有M個機器，有N個任務。每個任務必須在Si 或者以後開始做，在Ei 或者之前完成，完成任務必須處理Pi 個時間單位。其中，每個任務可以在任意（空閒）機器上工作，每個機器的同一時刻只能工作一個任務，每個任務在同一時刻只能被一個機器工作，而且任務做到一半可以打斷，拿去其他機器做。問：能否在規定時間內把任務做完。

思路：建圖是關鍵，我們可以選擇0為源點，然後源點與每個任務都連一條邊，容量為要求的天數p,然後每個任務都與相應的時間點連邊，邊容量為1，最後我們要確定匯點，匯點可以取vt=maxtime+n+1(其中maxtime為結束時間的最大值，n為任務數），這樣確定好匯點之後，再在每個時間點與匯點之間連邊，邊容量為m,為機器數(表示每個時間點最多可以有m台機器處理任務)，最後判斷sum(for all pi)==?SAP即可。

 

#include
#include
#include
using namespace std;
#define captype int

const int MAXN = 1010;   //點的總數
const int MAXM = 520010;    //邊的總數
const int INF = 1<<30;
struct EDG{
    int to,next;
    captype cap,flow;
} edg[MAXM];
int eid,head[MAXN];
int gap[MAXN];  //每種距離(或可認為是高度)點的個數
int dis[MAXN];  //每個點到終點eNode 的最短距離
int cur[MAXN];  //cur[u] 表示從u點出發可流經 cur[u] 號邊

void init(){
    eid=0;
    memset(head,-1,sizeof(head));
}
//有向邊 三個參數，無向邊4個參數
void addEdg(int u,int v,captype c,captype rc=0){
    edg[eid].to=v; edg[eid].next=head[u];
    edg[eid].cap=c; edg[eid].flow=0; head[u]=eid++;

    edg[eid].to=u; edg[eid].next=head[v];
    edg[eid].cap=rc; edg[eid].flow=0; head[v]=eid++;
}
//預處理eNode點到所有點的最短距離
void BFS(int sNode, int eNode){
    queueq;
    memset(gap,0,sizeof(gap));
    memset(dis,-1,sizeof(dis));
    gap[0]=1;
    dis[eNode]=0;
    q.push(eNode);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=head[u]; i!=-1; i=edg[i].next){
            int v=edg[i].to;
            if(dis[v]==-1){
                dis[v]=dis[u]+1;
                gap[dis[v]]++;
                q.push(v);
            }
        }
    }
}
int S[MAXN];    //路徑棧，存的是邊的id號
captype maxFlow_sap(int sNode,int eNode, int n){
    BFS(sNode, eNode);              //預處理eNode到所有點的最短距離
    if(dis[sNode]==-1) return 0;    //源點到不可到達匯點
    memcpy(cur,head,sizeof(head));

    int top=0;  //棧頂
    captype ans=0;  //最大流
    int u=sNode;
    while(dis[sNode]edg[S[i]].cap-edg[S[i]].flow){
                Min=edg[S[i]].cap-edg[S[i]].flow;
                inser=i;
            }
            for(int i=0; i0 && dis[u]==dis[v]+1){
                flag=true;
                cur[u]=i;
                break;
            }
        }
        if(flag){
            S[top++] = cur[u];  //加入一條邊
            u=v;
            continue;
        }
        //如果上面沒有找到一個可流的相鄰點，則改變出發點u的距離（也可認為是高度）為相鄰可流點的最小距離+1
        int Mind= n;
        for(int i=head[u]; i!=-1; i=edg[i].next)
        if(edg[i].cap-edg[i].flow>0 && Mind>dis[edg[i].to]){
            Mind=dis[edg[i].to];
            cur[u]=i;
        }
        gap[dis[u]]--;
        if(gap[dis[u]]==0) return ans;  //當dis[u]這種距離的點沒有了，也就不可能從源點出發找到一條增廣流路徑
                                        //因為匯點到當前點的距離只有一種，那麼從源點到匯點必然經過當前點，然而當前點又沒能找到可流向的點，那麼必然斷流
        dis[u]=Mind+1;      //如果找到一個可流的相鄰點，則距離為相鄰點距離+1，如果找不到，則為n+1
        gap[dis[u]]++;
        if(u!=sNode) u=edg[S[--top]^1].to;  //退一條邊

    }
    return ans;
}
int main(){
    int T,cas=0,n,m;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        init();
        int maxtime=0,sump=0;
        for(int i = 1; i<=n; i++){
            int P,S,E;
            scanf("%d%d%d",&P,&S,&E);

            sump += P;   //總流量
            if(E>maxtime)
                maxtime = E;

            addEdg(0,i,P);  //源點0到任務i的最大流量為P
            for(int j=S; j<=E; j++)
                addEdg(i,n+j,1);   //任務i到時間點j+n，邊最大容量為1
        }
        int t=maxtime + n +1;
        for(int j=1; j<=maxtime; j++)
            addEdg(j+n,t,m);	//每個時間點到匯點t，邊最大容量為m

        printf("Case %d: %s\n\n",++cas,maxFlow_sap(0,t,t)==sump?"Yes":"No");
    }
}