題目大意: 有m(1<=m<=1000)個豬圈,n(1<=n<=100)名客人,第i個豬圈有ci頭豬. 第i人第i天去買豬,有ki把鑰匙,最多買bi頭豬. 第i天的時候,鑰匙對應的豬圈會打開,這個時候可以對豬圈任意分配豬的數量(和不會超過打開的豬圈的豬的數量之和.) 問最多能賣多少豬. 題目思路: (1)建立一個超級源點和一個超級匯點. (2)源點向所有豬圈建邊,容量為豬圈初始的豬的數量,這樣保證了網絡中的流量不會超過豬的總數量. (3)所有客人向匯點建邊,容量為其需求量,這樣保證了到匯點的流量不會超過總需求量. (3)豬圈向擁有其鑰匙的人建邊,容量為無窮大,能流過去即可.www.2cto.com (4)先買的顧客向之後和他擁有相同鑰匙的顧客建邊,容量為無窮大,這樣使得前面豬圈交換的信息可以向下傳遞,以達到最優值. 代碼: [cpp] #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; }
