博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[USACO07OPEN]吃饭Dining
阅读量:5082 次
发布时间:2019-06-13

本文共 1914 字,大约阅读时间需要 6 分钟。

#include
#include
#include
#define N 501#define M N*Nusing namespace std;int src,decc,ans;int from[N],to[M],nxt[M],tot=1;int cap[M];int cur[N],lev[N];queue
q;void add(int u,int v,int f){ to[++tot]=v; nxt[tot]=from[u]; from[u]=tot; cap[tot]=f; to[++tot]=u; nxt[tot]=from[v]; from[v]=tot; cap[tot]=0;}bool bfs(){ while(!q.empty()) q.pop(); for(int i=src; i<=decc; i++) cur[i]=from[i],lev[i]=-1; q.push(src); lev[src]=0; int now; while(!q.empty()) { now=q.front(); q.pop(); for(int i=from[now]; i; i=nxt[i]) { if(lev[to[i]]==-1&&cap[i]>0) { lev[to[i]]=lev[now]+1; if(to[i]==decc) return true; q.push(to[i]); } } } return false;}int dinic(int now,int flow){ if(now==decc) return flow; int rest=0,delta; for(int &i=cur[now]; i; i=nxt[i]) { if(lev[to[i]]>lev[now]&&cap[i]>0) { delta=dinic(to[i],min(cap[i],flow-rest)); if(delta) { cap[i]-=delta; cap[i^1]+=delta; rest+=delta; if(rest==flow) break; } } } if(rest!=flow) lev[now]=-1; return rest;}int main(){ int n,f,d,fi,di,x; scanf("%d%d%d",&n,&f,&d); decc=(n<<1|1)+f+d+1; for(int i=1; i<=f; i++) add(src,(n<<1|1)+i,1); for(int i=1; i<=d; i++) add((n<<1|1)+f+i,decc,1); for(int i=1; i<=n; i++) add(i<<1,i<<1|1,1); for(int i=1; i<=n; i++) { scanf("%d%d",&fi,&di); for(int j=1; j<=fi; j++) { scanf("%d",&x); add((n<<1|1)+x,i<<1,1); } for(int j=1; j<=di; j++) { scanf("%d",&x); add(i<<1|1,(n<<1|1)+f+x,1); } } while(bfs()) ans+=dinic(src,N); printf("%d",ans);}

 

转载于:https://www.cnblogs.com/shandongs1/p/8093787.html

你可能感兴趣的文章
1005. Maximize Sum Of Array After K Negations
查看>>
自定义流水号。
查看>>
.Net下的进程间的通讯 -- Windows消息队列
查看>>
Linux下c开发 之 线程通信(转)
查看>>
时间复杂度分析
查看>>
Java 传递参数时,传递一个变量快还是传递一个实体类?
查看>>
解释器模式
查看>>
mysql增加字段,修改字段,增加索引等语句
查看>>
使用Charles进行网络请求抓包解析
查看>>
配置MySQL主从复制和读写分离
查看>>
STM32的bulk双缓冲传输速度的讨论,硬件的坑永远填不完
查看>>
有序数组寻找中位数以及寻找K大元素
查看>>
ES Reindex用java来实现
查看>>
模板复习
查看>>
MongoDB 自己定义函数
查看>>
关于Try/Catch 代码块
查看>>
解决虚拟机vmware安装64位系统“此主机支持 Intel VT-x,但 Intel VT-x 处于禁用状态”的问题...
查看>>
SQL 使用identity(int,1,1)来产生行号。
查看>>
springboot之Date格式化
查看>>
varnish解读
查看>>