1 条题解
-
0
C++ :
//SAPËã·¨ #include<stdio.h> #include<string.h> #include<algorithm> #define inf 9999999999 #define M 1007 #define MIN(a,b) a>b?b:a; using namespace std; struct E { int v,w,next; }edg[500000]; int dis[2000],gap[2000],head[2000],nodes; int sourse,sink,nn; void addedge(int u,int v,int w) { edg[nodes].v=v; edg[nodes].w=w; edg[nodes].next=head[u]; head[u]=nodes++; edg[nodes].v=u; edg[nodes].w=0; edg[nodes].next=head[v]; head[v]=nodes++; } int dfs(int src,int aug) { if(src==sink)return aug; int left=aug,mindis=nn; for(int j=head[src];j!=-1;j=edg[j].next) { int v=edg[j].v; if(edg[j].w) { if(dis[v]+1==dis[src]) { int minn=MIN(left,edg[j].w); minn=dfs(v,minn); edg[j].w-=minn; edg[j^1].w+=minn; left-=minn; if(dis[sourse]>=nn)return aug-left; if(left==0)break; } if(dis[v]<mindis) mindis=dis[v]; } } if(left==aug) { if(!(--gap[dis[src]]))dis[sourse]=nn; dis[src]=mindis+1; gap[dis[src]]++; } return aug-left; } int sap(int s,int e) { int ans=0; nn=e+1; memset(dis,0,sizeof(dis)); memset(gap,0,sizeof(gap)); gap[0]=nn; sourse=s; sink=e; while(dis[sourse]<nn) ans+=dfs(sourse,inf); return ans; } int main() { int n,f,d; while(scanf("%d%d%d",&n,&f,&d)!=EOF) { memset(head,-1,sizeof(head)); nodes=0; int s=0; int i,j; int t=f+2*n+1+d; int food,drink; int a,b; for(i=1;i<=n;i++) { scanf("%d%d",&food,&drink); for(j=1;j<=food;j++) { scanf("%d",&a); addedge(a,i+f,1);//食物和人 } for(j=1;j<=drink;j++) { scanf("%d",&b); addedge(i+f+n,f+2*n+b,1);//人和饮料 } } for(i=1;i<=f;i++) { addedge(s,i,1); } for(i=1;i<=d;i++) { addedge(f+2*n+i,t,1);//人和人 } for(i=1;i<=n;i++) { addedge(i+f,i+f+n,1); } int anss=sap(s,t); printf("%d\n",anss); } return 0; }
- 1
信息
- ID
- 934
- 时间
- 2000ms
- 内存
- 216MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者