| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 6672 | Accepted: 2348 |
Description
To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they're at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPF ≤ 1,000; minSPF ≤ maxSPF ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunburn; if the SPF rating is too high, the cow doesn't tan at all........
The cows have a picnic basket with L (1 ≤ L ≤ 2500) bottles of sunscreen lotion, each bottle i with an SPF rating SPF (1 ≤ SPF ≤ 1,000). Lotion bottle i can cover cover cows with lotion. A cow may lotion from only one bottle.
What is the maximum number of cows that can protect themselves while tanning given the available lotions?
Input
* Line 1: Two space-separated integers: C and L
* Lines 2..C+1: Line i describes cow i's lotion requires with two integers: minSPF and maxSPF
* Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPF and cover
Output
A single line with an integer that is the maximum number of cows that can be protected while tanning
Sample Input
3 2
3 10
2 5
1 5
6 2
4 1
Sample Output
2
Source
题意：N头牛,第I头需要一个SPF的范围是MinSPF~MaxSPF,m个bottle,每个bottle能给C头牛提供定值为P的SPF,求最多有多少头牛可以得到合适的SPF.
题解:设立超级源点S和超级汇点T，S向每个Bottle引一条容量为P的边，如果牛可以忍受这个bottle的SPF，那么就连一条容量为1的边，最后所有的牛像汇点引一条容量为1的边，求最大流即可。
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
#include <math.h>
#include <iostream>
#include <math.h>
using namespace std;
const int N = ;
const int INF = ;
struct Edge
{
int v,next;
int w;
} edge[N*N];
struct Cow{
int minSPF,maxSPF;
}cow[N/];
int head[N];
int level[N];
int tot;
void init()
{
memset(head,-,sizeof(head));
tot=;
}
void addEdge(int u,int v,int w,int &k)
{
edge[k].v = v,edge[k].w=w,edge[k].next=head[u],head[u]=k++;
edge[k].v = u,edge[k].w=,edge[k].next=head[v],head[v]=k++;
}
int BFS(int src,int des)
{
queue<int >q;
memset(level,,sizeof(level));
level[src]=;
q.push(src);
while(!q.empty())
{
int u = q.front();
q.pop();
if(u==des) return ;
for(int k = head[u]; k!=-; k=edge[k].next)
{
int v = edge[k].v;
int w = edge[k].w;
if(level[v]==&&w!=)
{
level[v]=level[u]+;
q.push(v);
}
}
}
return -;
}
int dfs(int u,int des,int increaseRoad){
if(u==des||increaseRoad==) return increaseRoad;
int ret=;
for(int k=head[u];k!=-;k=edge[k].next){
int v = edge[k].v,w=edge[k].w;
if(level[v]==level[u]+&&w!=){
int MIN = min(increaseRoad-ret,w);
w = dfs(v,des,MIN);
if(w > )
{
edge[k].w -=w;
edge[k^].w+=w;
ret+=w;
if(ret==increaseRoad) return ret;
}
else level[v] = -;
if(increaseRoad==) break;
}
}
if(ret==) level[u]=-;
return ret;
}
int Dinic(int src,int des)
{
int ans = ;
while(BFS(src,des)!=-) ans+=dfs(src,des,INF);
return ans;
}
int main()
{
int c,l;
scanf("%d%d",&c,&l);
init();
int src = ,des = c+l+;
for(int i=; i<=c; i++)
{
scanf("%d%d",&cow[i].minSPF,&cow[i].maxSPF);
addEdge(i+l,des,,tot);
}
for(int i=; i<=l; i++)
{
int a,b;
scanf("%d%d",&a,&b);
addEdge(src,i,b,tot);
for(int j=; j<=c; j++)
{
if(a>=cow[j].minSPF&&a<=cow[j].maxSPF)
{
addEdge(i,j+l,,tot);
}
}
}
printf("%d\n",Dinic(src,des));
}