首页 > 代码库 > BZOJ 1707: [Usaco2007 Nov]tanning分配防晒霜
BZOJ 1707: [Usaco2007 Nov]tanning分配防晒霜
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;}
BZOJ 1707: [Usaco2007 Nov]tanning分配防晒霜
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。