#include<cstdio>
#include<iostream>
#include<algorithm>
#define inf 99999999
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;
int S,sink,oo,T,cnt,n,ans,sum;
int c[1000001];
int H[1000001];
int d[1000001];
struct edge{
int u,v,c,next;
};
edge a[1000001];
void init()
{
int i;
for(i=0;i<1000001;i++)
H[i]=-1;
cnt=0;
}
void add(int u,int v,int c)
{
a[cnt].u=u;
a[cnt].v=v;
a[cnt].c=c;
a[cnt].next=H[u];
H[u]=cnt++;
}
void build(int u,int v,int c)
{
add(u,v,c);
add(v,u,0);
}
int dfs(int u,int flow)
{
if(u==sink)
return flow;
int Mindis = T;
int tt,res=0,delta;
for(tt=H[u];~tt;tt=a[tt].next)
{
int &v=a[tt].v,&c=a[tt].c;
if(c)
{
if(d[u]==d[v]+1)
{
delta=dfs(v,min(flow,c));
c-=delta;
a[tt^1].c+=delta;
res+=delta;
flow-=delta;
if(d[S]>=T) return res;
if(!flow)
break;
}
if(d[v]<Mindis)
Mindis=d[v];
}
}
if(!res)
{
if(!--c[d[u]]) d[S]=T;
d[u] = Mindis+1;
c[d[u]]++;
}
return res;
}
void sap()
{
c[0]=T;
memset(d,0,sizeof(d));
memset(c,0,sizeof(c));
while(d[S]<T)
ans+=dfs(S,oo);
}
int main()
{
int i,m,t,pi,si,ei,Max,j;
int cases=1;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
S=0;
ans=0;
Max=0;
oo=inf;
sum=0;
init();
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&pi,&si,&ei);
sum+=pi;
build(S,i,pi);
for(j=si;j<=ei;++j)
build(i,n+j,1);
Max=max(Max,ei);
}
sink=n+Max+1;
T=n+Max+2;
for(i=1;i<=Max;i++)
{
build(n+i,sink,m);
}
sap();
if(ans==sum)
printf("Case %d: Yes\n\n",cases++);
else
printf("Case %d: No\n\n",cases++);
}
return 0;
}
转载于:https://www.cnblogs.com/ray007great/archive/2013/05/06/3063493.html
