题目大概说有n只猴子，猴子们在某个时间段需要喝vi时间的水，各个单位时间段最多允许m只猴子同时喝水，问猴子们能否成功喝水并输出一个可行的方案，输出方案的时间段区间要从小到大排序并且合并连续的区间。
首先应该能联想到这是最大流的模型。猴子有100只，不过区间的点达到50W，这时考虑离散化，离散化后最多就200个点也就是199个区间。
- 于是猴子与区间可以作为容量网络的点，新建源点和汇点。
- 源点向猴子连容量vi的边，区间向汇点连容量为区间包含单位时间段数*m的边。
- 各个猴子喝水时间段包含的区间，由猴子向区间连容量为区间包含单位时间段数的边。
这个建图很容易想到。不过这题不是这么容易就解决了。。还要输出方案。
在残量网络中能知道各个猴子使用的哪几个区间中的多少个时间段。可以通过这个信息去构造出一个可行的方案：从头到尾再回到头循环地把区间内各个时间段安排给各个猴子。
最后得到区间还要排序下。。然后合并连续区间。。我WA了好久，搞了好久。。合并区间写错了。。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define INF (1<<30)
#define MAXN 333
#define MAXM 333*666 struct Edge{
int v,cap,next;
}edge[MAXM];
int vs,vt,NE,NV;
int head[MAXN]; void addEdge(int u,int v,int cap){
edge[NE].v=v; edge[NE].cap=cap;
edge[NE].next=head[u]; head[u]=NE++;
edge[NE].v=u; edge[NE].cap=;
edge[NE].next=head[v]; head[v]=NE++;
} int level[MAXN];
int gap[MAXN];
void bfs(){
memset(level,-,sizeof(level));
memset(gap,,sizeof(gap));
level[vt]=;
gap[level[vt]]++;
queue<int> que;
que.push(vt);
while(!que.empty()){
int u=que.front(); que.pop();
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(level[v]!=-) continue;
level[v]=level[u]+;
gap[level[v]]++;
que.push(v);
}
}
} int pre[MAXN];
int cur[MAXN];
int ISAP(){
bfs();
memset(pre,-,sizeof(pre));
memcpy(cur,head,sizeof(head));
int u=pre[vs]=vs,flow=,aug=INF;
gap[]=NV;
while(level[vs]<NV){
bool flag=false;
for(int &i=cur[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(edge[i].cap && level[u]==level[v]+){
flag=true;
pre[v]=u;
u=v;
//aug=(aug==-1?edge[i].cap:min(aug,edge[i].cap));
aug=min(aug,edge[i].cap);
if(v==vt){
flow+=aug;
for(u=pre[v]; v!=vs; v=u,u=pre[u]){
edge[cur[u]].cap-=aug;
edge[cur[u]^].cap+=aug;
}
//aug=-1;
aug=INF;
}
break;
}
}
if(flag) continue;
int minlevel=NV;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(edge[i].cap && level[v]<minlevel){
minlevel=level[v];
cur[u]=i;
}
}
if(--gap[level[u]]==) break;
level[u]=minlevel+;
gap[level[u]]++;
u=pre[u];
}
return flow;
} int need[],x[],y[];
int point[],pn; struct Interval{
int x,y;
bool operator<(const Interval &i)const{
return x<i.x;
}
}interval[]; int main(){
int cse=,n,m;
while(~scanf("%d",&n) && n){
scanf("%d",&m);
pn=; int tot=;
for(int i=; i<=n; ++i){
scanf("%d%d%d",need+i,x+i,y+i);
tot+=need[i];
point[pn++]=x[i];
point[pn++]=y[i];
}
sort(point,point+pn);
pn=unique(point,point+pn)-point; vs=; vt=n+pn+; NV=vt+; NE=;
memset(head,-,sizeof(head)); for(int i=; i<pn; ++i){
addEdge(i+n,vt,m*(point[i]-point[i-]));
}
for(int i=; i<=n; ++i){
addEdge(vs,i,need[i]);
int from=lower_bound(point,point+pn,x[i])-point;
int to=lower_bound(point,point+pn,y[i])-point;
for(int j=from+; j<=to; ++j){
addEdge(i,j+n,point[j]-point[j-]);
}
} if(ISAP()!=tot){
printf("Case %d: No\n",++cse);
continue;
}
printf("Case %d: Yes\n",++cse); int cnt[]={}; for(int u=; u<=n; ++u){
int in=;
for(int i=head[u]; i!=-; i=edge[i].next){
if(i& || edge[i^].cap==) continue;
int k=edge[i].v-n,tot=point[k]-point[k-];
if(cnt[k]+edge[i^].cap<=tot){
interval[in].x=point[k-]+cnt[k];
interval[in].y=point[k-]+cnt[k]+edge[i^].cap;
++in;
cnt[k]+=edge[i^].cap;
}else if(cnt[k]==tot){
interval[in].x=point[k-];
interval[in].y=point[k-]+edge[i^].cap;
++in;
cnt[k]=edge[i^].cap;
}else{
interval[in].x=point[k-]+cnt[k];
interval[in].y=point[k];
++in;
cnt[k]+=edge[i^].cap; cnt[k]-=tot;
interval[in].x=point[k-];
interval[in].y=point[k-]+cnt[k];
++in;
}
}
sort(interval,interval+in);
int tot=in;
for(int i=; i<in; ++i){
if(interval[i].x==interval[i-].y){
--tot;
}
}
printf("%d",tot);
for(int i=; i<in; ){
int j=i+;
while(j<in && interval[j-].y==interval[j].x){
++j;
}
printf(" (%d,%d)",interval[i].x,interval[j-].y);
i=j;
}
putchar('\n');
}
}
return ;
}