HDU3572Task Schedule(最大流 ISAP比較快)建圖方法不錯
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");
}
}
