题目链接:http://acm.nbu.edu.cn/v1.0/Problems/Problem.php?pid=2427
题目大意:
有m(1<=m<=1000)个猪圈,n(1<=n<=100)名客人,第i个猪圈有ci头猪.
第i人第i天去买猪,有ki把钥匙,最多买bi头猪.
第i天的时候,钥匙对应的猪圈会打开,这个时候可以对猪圈任意分配猪的数量(和不会超过打开的猪圈的猪的数量之和.)
问最多能卖多少猪.
题目思路:
(1)建立一个超级源点和一个超级汇点.
(2)源点向所有猪圈建边,容量为猪圈初始的猪的数量,这样保证了网络中的流量不会超过猪的总数量.
(3)所有客人向汇点建边,容量为其需求量,这样保证了到汇点的流量不会超过总需求量.
(3)猪圈向拥有其钥匙的人建边,容量为无穷大,能流过去即可.
(4)先买的顾客向之后和他拥有相同钥匙的顾客建边,容量为无穷大,这样使得前面猪圈交换的信息可以向下传递,以达到最优值.
代码:
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle (l+r)>>1
#define eps (1e-8)
#define clr_all(x,c) memset(x,c,sizeof(x))
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))
#define MOD 1000000009
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define _max(x,y) (((x)>(y))? (x):(y))
#define _min(x,y) (((x)<(y))? (x):(y))
#define _abs(x) ((x)<0? (-(x)):(x))
#define getmin(x,y) (x= ((x)<0 || (y)<(x))? (y):(x))
#define getmax(x,y) (x= ((y)>(x))? (y):(x))
template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}
int TS,cas=1;
const int M=1100+5;
int n,m;
struct sap{
typedef int type;
struct edge{
int to,next;
type flow;
}edg[999999];
int n,m;
int g[M],cur[M],pre[M];
int dis[M],gap[M];
int q[M],head,tail;
void init(int _n){n=_n,m=0,clr_all(g,-1);}
void insert(int u,int v,type f,type c=0){
edg[m].to=v,edg[m].flow=f,edg[m].next=g[u],g[u]=m++;
edg[m].to=u,edg[m].flow=0,edg[m].next=g[v],g[v]=m++;
}
bool bfs(int s,int t){
clr(gap,0,n),clr(dis,-1,n);
gap[dis[t]=0]++,dis[s]=-1;
for(q[head=tail=0]=t;head<=tail;){
int u=q[head++];
for(int i=g[u];i!=-1;i=edg[i].next){
edge& e=edg[i],ee=edg[i^1];
if(dis[e.to]==-1 && ee.flow>0){
gap[dis[e.to]=dis[u]+1]++;
q[++tail]=e.to;
}
}
}
return dis[s]!=-1;
}
type maxFlow(int s,int t){
if(!bfs(s,t)) return 0;
type res=0,a;
int i;
for(i=0;i<n;i++) cur[i]=g[i];
pre[s]=s,cur[s]=g[s],cur[t]=g[t];
for(int u=s;dis[s]<n;){
if(u==t){
for(a=-1;u!=s;u=pre[u])
getmin(a,edg[cur[pre[u]]].flow);
for(u=t;u!=s;u=pre[u]){
edg[cur[pre[u]]].flow-=a;
edg[cur[pre[u]]^1].flow+=a;
}
res+=a;
}
bool ok=0;
for(i=cur[u];i!=-1;i=edg[i].next){
edge& e=edg[i];
if(dis[u]==dis[e.to]+1 && e.flow>0){
cur[u]=i,pre[e.to]=u,u=e.to;
ok=1;break;
}
}
if(ok) continue;
int mindis=n-1;
for(i=g[u];i!=-1;i=edg[i].next){
edge& e=edg[i];
if(mindis>dis[e.to] && e.flow>0)
mindis=dis[e.to],cur[u]=i;
}
if(--gap[dis[u]]==0) break;
gap[dis[u]=mindis+1]++,u=pre[u];
}
return res;
}
}p;
int tmp[M][111],sz[M];
bool vis[111][111];
void run(){
int i,j;
int k,a,b;
p.init(n+m+2);
for(i=1;i<=m;i++){
scanf("%d",&b);
p.insert(0,n+i,b);
}
clr_all(sz,0);
for(i=1;i<=n;i++){
scanf("%d",&k);
while(k--){
scanf("%d",&a);
p.insert(n+a,i,INF);
tmp[a][sz[a]++]=i;
}
scanf("%d",&b);
p.insert(i,n+m+1,b);
}
clr_all(vis,0);
for(i=1;i<=m;i++){
for(j=1;j<sz[i];j++){
int u=tmp[i][j-1],v=tmp[i][j];
if(!vis[u][v]) vis[u][v]=1,p.insert(u,v,INF);
}
}
printf("%d\n",p.maxFlow(0,n+m+1));
}
void preSof(){
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
preSof();
//run();
while(~scanf("%d%d",&m,&n)) run();
//for(scanf("%d",&TS);cas<=TS;cas++) run();
return 0;
}
分享到:
相关推荐
NBU介绍NBU介绍NBU介绍NBU介绍NBU介绍 NBU介绍NBU介绍NBU介绍NBU介绍NBU介绍 NBU介绍NBU介绍NBU介绍NBU介绍NBU介绍 NBU介绍NBU介绍NBU介绍NBU介绍NBU介绍
NBU架构介绍 NBU架构介绍 NBU架构介绍
NBU Netbackup veritas symantec 5230 备份一体机
NBU 备份mysql
Veritas NetBackup(NBU) NBU8.2 AIR 部署文档,经过实践部署可实现异地灾备备份方案
用NBU提供的插件调用VMware提供的IO Filter API,实现虚拟机复制。插件主要包含针对NBU不同的版本以及ESXi不同的版本。 以下是插件的具体安装要求: • Datastores supported: VMFS, NFS, vVol, vSAN • File-system...
NBU TRAINNING:NBU 培训.pdf
Netbackup的安装简介,含有一个NBU的序列号,希望对你有帮助
Linux下NBU客户端安装图文教程.docx Linux下NBU客户端安装图文教程.docx
NBU安装部署图文版操作手册,NBU安装部署图文版操作手册
NBU windows平台的搭建,此视频主要讲解NBU在windows环境下的搭建。
Veritas NetBackup(NBU) NBU8.2 AIR 部署文档,经过实践部署可实现异地灾备备份方案
NBU 7.1 windows下NBU 管理手册
NBU For windows
NBU7.7.3手册NBU7.7.3手册NBU7.7.3手册NBU7.7.3手册NBU7.7.3手册NBU7.7.3手册
NBU备份双击操作安装配置,如何搭建NBU服务端,配置策略,配置服务器,配置存储池,共享存储,NBU还是比较不错的一款数据库备份软件,支持SQL,MYSQL,ORACLE等等
NBU 全模块授权 供大家学习搭建测试环境,不能用于商业活动。
NBU 5200.doc
NBU7备份虚拟机,描述了NBU备份虚拟机的过程
nbu 配置相关 。