程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU3572Task Schedule(最大流 ISAP比較快)建圖方法不錯

HDU3572Task Schedule(最大流 ISAP比較快)建圖方法不錯

編輯:關於C++

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


 


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved