一共有n个猪圈,m个客人,一开始每个猪圈都有一定数量的猪猪。每个客人会打开一些猪圈,带走最多为某一个数量的猪猪,剩下的猪猪可以任意分配在这些开了的猪圈里面,然后重新关上。问所有的客人最多可以带走多少猪猪?
网络流建模。其实每个猪圈如果被人开过了,那么下次再有人来访问这个猪圈的时候,相当于从上一个人那里得到的流量,这样我们可以不考虑猪圈,只考虑客人建点即可,假设f[i]保存i个猪圈上一次是被哪一些客人打开的,那么第j个客人再来此猪圈的时候,相当于从上一个客人手中得到的猪猪了。
一开始源点为0,从那里得到初始猪猪个数的流量。最后就是跑最大流即可。
这样建模就可以A了。
召唤代码君:
#include <iostream> #include <cstdio> #include <cstring> #define maxn 2222 #define maxm 2222222 using namespace std; int next[maxm],to[maxm],c[maxm],first[maxn],edge; int d[maxn],tag[maxn],pos[maxn],TAG=520; bool can[maxn]; int Q[maxm],bot,top; int s,t,n,m,ans,a[maxn],f[maxn],A,B; void _init() { for (int i=1; i<=n; i++) scanf("%d",&a[i]); ans=s=0,t=m+1,edge=-1; for (int i=s; i<=t; i++) first[i]=-1,f[i]=s; } void addedge(int U,int V,int W) { edge++; to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge; edge++; to[edge]=U,c[edge]=0,next[edge]=first[V],first[V]=edge; } bool bfs() { Q[bot=top=1]=t,tag[t]=++TAG,d[t]=0; while (bot<=top) { int cur=Q[bot++]; for (int i=first[cur]; i!=-1; i=next[i]) if (c[i^1]>0 && tag[to[i]]!=TAG) { tag[to[i]]=TAG,can[to[i]]=false; Q[++top]=to[i],d[to[i]]=d[cur]+1; if (to[i]==s) return true; } } return false; } int dfs(int cur,int num) { if (cur==t) return num; int tmp=num,k; for (int i=first[cur]; i!=-1; i=next[i]) if (c[i]>0 && tag[to[i]]==TAG && d[to[i]]==d[cur]-1 && !can[to[i]]) { k=dfs(to[i],min(num,c[i])); if (k) num-=k,c[i]-=k,c[i^1]+=k; if (!num) break; } if (num) can[cur]=true; return tmp-num; } int main() { while (scanf("%d%d",&n,&m)!=EOF) { _init(); for (int i=1; i<=m; i++) { scanf("%d",&A); while (A--) { scanf("%d",&B); if (!f[B]) addedge(f[B],i,a[B]); else addedge(f[B],i,~0U>>1); f[B]=i; } scanf("%d",&A); addedge(i,t,A); } while (bfs()) ans+=dfs(s,~0U>>1); printf("%d\n",ans); } return 0; }