[文章目录]
Description
Emmy在一个养猪场工作。这个养猪场有M个锁着的猪圈，但Emmy并没有钥匙。顾客会到养猪场来买猪，一个接着一个。每一位顾客都会有一些猪圈的钥匙，他们会将这些猪圈打开并买走固定数目的猪。 所有顾客有的钥匙和他们需要买猪的数量在事先都告诉了Emmy，于是Emmy要订一个计划，使得卖出去的猪最多。 买卖的过程是这样的：一个顾客前来，并打开所有他可以打开的猪圈。然后Emmy从这些猪圈里牵出固定数目的猪卖给顾客（最多只能和顾客需要数相等），并可以重新安排这些开着的猪圈中的猪。 每个猪圈可以存放任意数目的猪。 写一个程序，使得Emmy能够卖出去尽可能多的猪。m<=1000,n<=100
每天建m个节点，然后将该天可行牧场向购买者连边，购买者向汇点连一条边流量为k。然后购买者再向下一天的牧场连边。最大流即为答案。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,s,t,ans;
const int inf=0x3f3f3f3f;
int head[102000],to[801000],nxt[801000],cnt=1,f[801000];
void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
int dis[102000];
queue<int>q;
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-1,sizeof dis);
dis[s]=0; q.push(s); int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]<0)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(tmp,f[i]));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d%d",&n,&m);
int cc=n*m,i,j,x,y; s=cc+m+1,t=s+1;
for(i=1;i<=n;i++)
{
scanf("%d",&x);
add(s,i,x);
}
for(i=1;i<=m;++i)
{
scanf("%d",&x);
if(i!=m) for(j=1;j<=n;j++) add(j+(i-1)*n,j+i*n,inf);
while(x--)
{
scanf("%d",&y);
add(y+(i-1)*n,cc+i,inf);
if(i!=m) add(cc+i,y+i*n,inf);
}
scanf("%d",&x);
add(cc+i,t,x);
}
while(bfs()) ans+=dinic(s,inf);
printf("%d",ans);
return 0;
}