Description
奶牛们计划着去海滩上享受日光浴。为了避免皮肤被阳光灼伤，所有C(1 <= C <= 2500)头奶牛必须在出门之前在身上抹防晒霜。第i头奶牛适合的最小和最 大的SPF值分别为minSPF_i和maxSPF_i(1 <= minSPF_i <= 1,000; minSPF_i <= maxSPF_i <= 1,000)。如果某头奶牛涂的防晒霜的SPF值过小，那么阳光仍然能 把她的皮肤灼伤；如果防晒霜的SPF值过大，则会使日光浴与躺在屋里睡觉变得 几乎没有差别。为此，奶牛们准备了一大篮子防晒霜，一共L(1 <= L <= 2500)瓶。第i瓶 防晒霜的SPF值为SPF_i(1 <= SPF_i <= 1,000)。瓶子的大小也不一定相同，第i 瓶防晒霜可供cover_i头奶牛使用。当然，每头奶牛只能涂某一个瓶子里的防晒霜 ，而不能把若干个瓶里的混合着用。 请你计算一下，如果使用奶牛们准备的防晒霜，最多有多少奶牛能在不被灼 伤的前提下，享受到日光浴的效果？
Input
* 第1行: 2个用空格隔开的整数：C和L
* 第2..C+1行: 第i+1行给出了适合第i头奶牛的SPF值的范围：minSPF_i以及 maxSPF_i * 第C+2..C+L+1行: 第i+C+1行为了第i瓶防晒霜的参数：SPF_i和cover_i，两个 数间用空格隔开。
Output
* 第1行: 输出1个整数，表示最多有多少头奶牛能享受到日光浴
题解：
好像有贪心.
网络流水了过去.
S向每头牛连边容量为1,每头牛向可以用的防晒霜连边,容量为1,每个防晒霜向T连边容量为Cover.
S-T最大流即为答案.
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
//by zrt
//problem:
using namespace std;
int c,l;
int spf[2505];
int minn[2505];
int maxx[2505];
int S,T;
int H[5505],X[4000000],P[4000000],flow[4000000],tot;
inline void add(int x,int y,int z){
P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;
}
int d[5505];
queue<int> q;
bool bfs(){
memset(d,0,sizeof d);
d[S]=1;
while(!q.empty()) q.pop();
q.push(S);
int x;
while(!q.empty()){
x=q.front();q.pop();
if(x==T) return 1;
for(int i=H[x];i;i=X[i]){
if(flow[i]>0&&!d[P[i]]){
d[P[i]]=d[x]+1;
q.push(P[i]);
}
}
}
return 0;
}
int dfs(int x,int a){
if(x==T||a==0) return a;
int f=a,tmp;
for(int i=H[x];i;i=X[i]){
if(flow[i]>0&&d[P[i]]==d[x]+1){
tmp=dfs(P[i],min(flow[i],a));
a-=tmp;
flow[i]-=tmp;
flow[i^1]+=tmp;
if(!a) break;
}
}
if(f==a) d[x]=-1;
return f-a;
}
int Dinic(){
int f=0;
while(bfs()){
f+=dfs(S,1<<30);
}
return f;
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
tot=1;
S=5504,T=5503;
scanf("%d%d",&c,&l);
for(int i=1;i<=c;i++) scanf("%d%d",&minn[i],&maxx[i]),add(S,i,1),add(i,S,0);
for(int i=1,x;i<=l;i++) scanf("%d%d",&spf[i],&x),add(i+c,T,x),add(T,i+c,0);
for(int i=1;i<=c;i++){
for(int j=1;j<=l;j++){
if(minn[i]<=spf[j]&&spf[j]<=maxx[i]){
add(i,j+c,1);
add(j+c,i,0);
}
}
}
printf("%d\n",Dinic());
return 0;
}