| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 20759 | Accepted: 9488 |
Description
Input
Output
Sample Input
3 3 3 1 10 2 1 2 2 2 1 3 3 1 2 6
Sample Output
7
Source
暴力建图：
一看到题，最先想到的是要分层，以每个顾客为一层，该顾客可以打开的猪圈向该顾客连边，每层向下一层对应的猪圈以及能够相互之间调整的猪圈连边，求最大流。这样构图本身并没有错，但是数据范围是n<=100 m<=1000 图中的节点数会超过100000，时间上绝对不够
正确建图：
顾客之间连边.
新增源点s，汇点t，对于每个顾客来说，如果他是第一个打开某猪圈的，则从s向他连一条容量为该猪圈初始值的弧，如果与源点的流量已经不是0，则合并，如果不是第一个，则从上一个打开该猪圈的顾客向这个顾客连一条容量为+oo的弧，每个顾客向汇点连一条容量为该顾客希望购买的猪的数量的弧
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> using namespace std; const int N=2250; const int inf=0x3f3f3f3f; struct edge{int v,cap,next;}e[N*8];int tot=1; int n,m,k,S,T,cnt,head[N],last[N],dis[N],val[N],q[N*8]; void add(int x,int y,int z){ e[++tot].v=y;e[tot].cap=z;e[tot].next=head[x];head[x]=tot; e[++tot].v=x;e[tot].cap=0;e[tot].next=head[y];head[y]=tot; } void mapping(){ S=0,T=m+k+1;n=m; for(int i=1,w;i<=m;i++){ scanf("%d",&w); add(S,i,w); last[i]=i; } for(int i=1,w,v,cas;i<=k;i++){ n++; for(scanf("%d",&cas);cas--;){ scanf("%d",&v); add(last[v],n,inf); last[v]=n; } scanf("%d",&w); add(n,T,w); } } bool bfs(){ for(int i=S;i<=T;i++) dis[i]=-1; int h=0,t=1;dis[S]=0;q[t]=S; while(h!=t){ int x=q[++h]; for(int i=head[x];i;i=e[i].next){ if(dis[e[i].v]==-1&&e[i].cap){ dis[e[i].v]=dis[x]+1; if(e[i].v==T) return 1; q[++t]=e[i].v; } } } return 0; } int dfs(int x,int f){ if(x==T) return f; int used=0,t; for(int i=head[x];i;i=e[i].next){ if(e[i].cap&&dis[e[i].v]==dis[x]+1){ t=dfs(e[i].v,min(e[i].cap,f)); e[i].cap-=t;e[i^1].cap+=t; used+=t;f-=t; if(!f) return used; } } if(!used) dis[x]=-1; return used; } void dinic(){ int ans=0; while(bfs()) ans+=dfs(S,inf); printf("%d\n",ans); } void init(){ tot=1; memset(head,0,sizeof head); } int main(){ while(scanf("%d%d",&m,&k)==2){ init(); mapping(); dinic(); } return 0; }
原文：http://www.cnblogs.com/shenben/p/6374464.html