Task Schedule
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5550 Accepted Submission(s): 1786
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.
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.
Print a blank line after each test case.
4 3
1 3 5
1 1 4
2 3 7
3 5 9
2 2
2 1 3
1 2 2
Case 2: Yes
题意：有M个机器。有N个任务。
每一个任务必须在Si
或者以后開始做，在Ei 或者之前完毕，完毕任务必须处理Pi 个时间单位。
当中，每一个任务能够在随意（空暇）机器上工作。每一个机器的同一时刻仅仅能工作一个任务，
每一个任务在同一时刻仅仅能被一个机器工作，并且任务做到一半能够打断，拿去其它机器做。
问：是否能在规定时间内把任务做完。
思路:这题最大流最基本的就是建图。
刚開始学最大流的仅仅会模板的我果断不知道怎么建图。參考大神思路：
直接把0作为源点。最小的開始时间到最大的结束时间作为任务，0到任务的权值为机器个数；
从最大结束时间到它乘以2作为天数，每一个任务连范围内的全部时间点，权值为1，
最大结束时间乘以2加1作为汇点。每一个时间点到汇点权值为机器个数。判满流。
Dinic
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define M 1100
#define inf 0x3f3f3f3f
int head[M],dis[M];
int n,m,t,cnt;
struct node{
int u,v,next,w;
}mp[M*M];
void add(int u,int v,int w){//邻接表
mp[cnt].u=u;
mp[cnt].v=v;
mp[cnt].w=w;
mp[cnt].next=head[u];
head[u]=cnt++;
mp[cnt].u=v;//反向边
mp[cnt].v=u;
mp[cnt].w=0;
mp[cnt].next=head[v];
head[v]=cnt++;
}
int bfs(){
int s=0;
memset(dis,-1,sizeof(dis));
queue <int> q;
while(!q.empty()) q.pop();
dis[s]=0;
q.push(s);
while(!q.empty()){
s=q.front();
q.pop();
for(int i=head[s];i!=-1;i=mp[i].next){
int v=mp[i].v;
if(dis[v]==-1&&mp[i].w){
dis[v]=dis[s]+1;
if(v==t) return 1;//假设搜到汇点直接结束函数
q.push(v);
}
}
}
return 0;
}
int dfs(int s,int low){
if(s==t) return low;
int a,i,ans=0;
for(i=head[s];i!=-1;i=mp[i].next){
int v=mp[i].v;
if(mp[i].w && dis[v]==dis[s]+1 && (a=dfs(v,min(low,mp[i].w))) ){
mp[i].w-=a;
mp[i^1].w+=a;//反向边
ans+=a;//这两行是速度优化 ,我试了非常多次。写的话200多MS，
if(ans==low) break;//不写的话就超时
}
}
return ans;
}
int main(){
int T,i,j,t1,t2,sum,cas=1;
int s[505],e[505],q[505];
scanf("%d",&T);
while(T--){
sum=0; t1=inf; t2=-1;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d%d%d",&q[i],&s[i],&e[i]);
t1=min(s[i],t1);
t2=max(e[i],t2);
sum+=q[i];
}
memset(head,-1,sizeof(head));
cnt=0; t=t2*2+1;//t为超级汇点
for(i=t1;i<=t2;i++)
add(0,i,m);//超级源点0到每一个任务连线。每条线权值为机器个数
for(i=1;i<=n;i++){
for(j=s[i];j<=e[i];j++){
add(j,j+t2,1);//每一个任务和任务相关的每一天权值设为1
add(j+t2,t2*2+1,m);//每一天到汇点t2*2+1，设置成机器个数m。事实上这我也试了好多次。
// 设置成1，或者q每一个任务的持续的时间数，都能够AC，，好像不影响= =+
}
}
int ans=0,k;
while(bfs()){
while(k=dfs(0,inf))
ans+=k;
}
if(sum<=ans)//能完毕的话
printf("Case %d: Yes\n\n",cas++);
else printf("Case %d: No\n\n",cas++);
}
return 0;
}