先翻译一下吧(题面可以在原OJ上找)
Mirko在一个由M个锁着的猪舍组成的养猪场工作,Mirko无法解锁任何猪舍,因为他没有钥匙。客户纷纷来到农场。他们每个人都有一些猪舍的钥匙,并想购买一定数量的猪。
有关计划在特定日期访问农场的客户的所有数据都可以在清晨获得Mirko,以便他可以制定销售计划以最大化销售的猪数量。
更准确地说,程序如下:顾客到达,打开他有钥匙的所有猪舍,Mirko将所有未开封的猪舍中的一定数量的猪卖给他,如果Mirko想要的话,他可以将剩余的猪重新分配到解锁的猪舍。
每个猪舍都可以放置无限数量的猪。顾客来的顺序不能改变,猪舍在顾客走后锁上。
编写一个程序,找出当天可以卖出的最大猪数。
解析
这确实是网络流建图好题。
首先,顾客来的顺序很重要,
因为当一个拥有猪舍X的钥匙的顾客i来后,
下一个拥有X的钥匙的顾客j实际上也能买到i能买到的猪(因为其他猪舍的猪可以在i买后调整到X中)。
因此,将j和i连边即可,流量为INF。
然后,若i是第一个打开X的人,就将i和汇点T连边,流量为X的初始猪数。
最后,将源点与每个顾客连边,流量为顾客最多买的猪,
再跑最大流就行了!
上AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; inline int read(){
int sum=,f=;char ch=getchar();
while(ch>'' || ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){sum=sum*+ch-'';ch=getchar();}
return f*sum;
} const int INF=0x3f3f3f3f;
struct node{
int next,to,w;
}e[];
struct cus{
int ksum;/*钥匙数*/
int key[];/*钥匙*/
int sum;/*买猪的最大数*/
}c[];
int n,m,s,t;
int a[];
int head[],cnt=;
int d[],las[]/*i猪舍的上一个顾客*/; void add(int x,int y,int w){
// printf("from: %d to: %d\n",x,y);
e[++cnt].to=head[x];
e[cnt].next=y;
e[cnt].w=w;
head[x]=cnt;
} bool bfs(){
queue <int> que;
memset(d,,sizeof(d));
que.push(s);
d[s]=;
while(!que.empty()){
int x=que.front();
que.pop();
for(int i=head[x];i;i=e[i].to){
int k=e[i].next;
if(!e[i].w||d[k]) continue;
d[k]=d[x]+;
que.push(k);
}
}
return d[t];
} int dfs(int x,int mi){
if(x==t||!mi) return mi;
int ret=,a=;
for(int i=head[x];i;i=e[i].to){
int k=e[i].next;
if(!e[i].w||d[k]!=d[x]+) continue;
ret=dfs(k,min(mi,e[i].w));
a+=ret;mi-=ret;
e[i].w-=ret;
e[i^].w+=ret;
if(!mi) break; }
if(a) d[x]=-;
return a;
} void DINIC(){
int ans=;
while(bfs()){
int ret=dfs(s,INF);
ans+=ret;
}
printf("%d\n",ans);
} int main(){
m=read();n=read();
s=n+;t=n+;
for(int i=;i<=m;i++){
a[i]=read();
}
for(int i=;i<=n;i++){
c[i].ksum=read();
for(int j=;j<=c[i].ksum;j++){
c[i].key[j]=read();
}
c[i].sum=read();
add(s,i,c[i].sum);
add(i,s,); //与源点连边
}
for(int i=;i<=n;i++){
for(int j=;j<=c[i].ksum;j++){
int k=c[i].key[j];
if(!las[k]){
add(i,t,a[k]);
add(t,i,);
}
else{
add(i,las[k],INF);
add(las[k],i,);
}
las[k]=i;
}
}
DINIC();/*最大流*/
return ;
}