poj 3614(最大流)

Sunscreen

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 6682	Accepted: 2350

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 ≤ minSPFi ≤ 1,000; minSPFi≤ maxSPFi ≤ 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 SPFi (1 ≤ SPFi ≤ 1,000). Lotion bottle i can cover coveri 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: minSPFi and maxSPFi 

* Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPFi and coveri

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

題意：N頭牛,第I頭需要一個SPF的範圍是MinSPF~MaxSPF,m個bottle,每個bottle能給C頭牛提供定值為P的SPF,求最多有多少頭牛可以得到合适的SPF.

解題思路：最大流，m個bottle與源點相連，容量為c，表示每個bottle能夠提供給c頭牛，n頭牛與彙點連容量為1的邊，限制了每頭牛隻能夠一個bottle，每個bottle的SPF隻要在牛的SPF範圍内，就連一條容量為1的邊，表示能提供1頭牛使用。

這個題目有點卡模闆：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int maxn = 5005;
const int inf = 0x3f3f3f3f;
struct Edge
{
	int to,next,flow;
}edge[maxn*maxn];
struct Node
{
	int minSPF,maxSPF;
}cow[maxn];
int n,m,cnt,pre[maxn],layer[maxn];

void addedge(int u,int v,int flow)
{
	edge[cnt].to = v;
	edge[cnt].flow = flow;
	edge[cnt].next = pre[u];
	pre[u] = cnt++;
	swap(u,v);
	edge[cnt].to = v;
	edge[cnt].flow = 0;
	edge[cnt].next = pre[u];
	pre[u] = cnt++;
}

bool bfs(int s,int t)
{
	queue<int> q;
	memset(layer,-1,sizeof(layer));
	layer[s] = 0;
	q.push(s);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		if(u == t) return true;
		for(int i = pre[u]; i != -1; i = edge[i].next)
		{
			int v = edge[i].to;
			if(layer[v] == -1 && edge[i].flow > 0)
			{
				layer[v] = layer[u] + 1;
				q.push(v);
			}
		}
	}
	return false;
}

int dfs(int u,int t,int maxflow)
{
	if(u == t || maxflow == 0) return maxflow;
	int uflow = 0;
	for(int i = pre[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].to;
		if(layer[v] == layer[u] + 1 && edge[i].flow > 0)
		{
			int flow = min(maxflow - uflow,edge[i].flow);
			flow = dfs(v,t,flow);
			if(flow > 0)
			{
				edge[i].flow -= flow;
				edge[i^1].flow += flow;
				uflow += flow;
				if(uflow == flow) break;
			}
			else layer[v] = -1;
		}
	}
	if(uflow == 0) layer[u] = -1;
	return uflow;
}

int dinic(int s,int t)
{
	int maxflow = 0;
	while(bfs(s,t) == true)
		maxflow += dfs(s,t,inf);
	return maxflow;
}

int main()
{
	int s,t,w,c;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		s = 0, t = n + m + 1;
		cnt = 0;
		memset(pre,-1,sizeof(pre));
		for(int i = 1; i <= n; i++)
		{
			scanf("%d%d",&cow[i].minSPF,&cow[i].maxSPF);
			addedge(m+i,t,1);
		}
		for(int i = 1; i <= m; i++)
		{
			scanf("%d%d",&w,&c);
			addedge(s,i,c);
			for(int j = 1; j <= n; j++)
				if(cow[j].minSPF <= w && w <= cow[j].maxSPF)
					addedge(i,m+j,1);
		}
		printf("%d\n",dinic(s,t));
	}
	return 0;
}