【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1711

【题目大意】

  每头牛都有一些喜欢的饮料和食物,
  现在有一些食物和饮料,但是每样只有一份,
  现在要求得到最多的牛使得都可以获得一份喜欢的饮料和一份喜欢的食物

【题解】

  为了避免一份牛占用过多的资源,我们对牛进行拆点,增加边作为限制,
  然后源点连接食物,汇点连接饮料,求最大流即可。

【代码】

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAX_V=1000;
struct edge{int to,cap,rev;};
vector<edge> G[MAX_V];
int level[MAX_V],iter[MAX_V];
void add_edge(int from,int to,int cap){
G[from].push_back((edge){to,cap,G[to].size()});
G[to].push_back((edge){from,0,G[from].size()-1});
}
void bfs(int s){
memset(level,-1,sizeof(level));
queue<int> que;
level[s]=0;
que.push(s);
while(!que.empty()){
int v=que.front(); que.pop();
for(int i=0;i<G[v].size();i++){
edge &e=G[v][i];
if(e.cap>0&&level[e.to]<0){
level[e.to]=level[v]+1;
que.push(e.to);
}
}
}
}
int dfs(int v,int t,int f){
if(v==t)return f;
for(int &i=iter[v];i<G[v].size();i++){
edge &e=G[v][i];
if(e.cap>0&&level[v]<level[e.to]){
int d=dfs(e.to,t,min(f,e.cap));
if(d>0){
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}return 0;
}
int max_flow(int s,int t){
int flow=0;
for(;;){
bfs(s);
if(level[t]<0)return flow;
memset(iter,0,sizeof(iter));
int f;
while((f=dfs(s,t,INF))>0){
flow+=f;
}
}
}
int N,F,D;
int f[110],d[110];
int main(){
scanf("%d%d%d",&N,&F,&D);
for(int i=0;i<=N*2+F+D+1;i++)G[i].clear();
for(int x=1;x<=F;x++)add_edge(0,x+N*2,1);
for(int x=1;x<=D;x++)add_edge(x+N*2+F,N*2+F+D+1,1);
for(int i=1;i<=N;i++){
scanf("%d%d",&f[i],&d[i]);
for(int j=1;j<=f[i];j++){
int x;
scanf("%d",&x);
add_edge(x+N*2,i,1);
}
for(int j=1;j<=d[i];j++){
int x;
scanf("%d",&x);
add_edge(i+N,x+N*2+F,1);
}add_edge(i,i+N,1);
}printf("%d\n",max_flow(0,N*2+F+D+1));
return 0;
}

  

最新文章

  1. 数百个 HTML5 例子学习 HT 图形组件 – 拓扑图篇
  2. Moto C118 基于 Osmocom-BB 和 OpenBTS 搭建小型GSM短信基站
  3. 第4/24周 页面限制8060 bytes
  4. java AES 加密与解密
  5. css定位的简单总结
  6. POJ 2965 The Pilots Brothers&#39; refrigerator 暴力 难度:1
  7. C++对象内存模型1(堆栈模型)
  8. Ngnix 安装、信号量、虚拟主机配置
  9. Vim 快捷键整理
  10. block,inline,inline-block
  11. angular中使用echart遇到的获取容器高度异常的问题记录
  12. Java虚拟机-类文件
  13. node模块之path——path.join和path.resolve的区别
  14. [转]每天一个linux命令(44):top命令
  15. 基于jQuery游戏网站焦点图轮播特效
  16. POSIX 消息队列 之 概述 链接方式
  17. 第182天:HTML5——地理定位
  18. 算法学习 并查集(Union-Find) (转)
  19. 容器控件JPanel的使用
  20. [JSOI2009]瓶子和燃料 BZOJ2257 数学

热门文章

  1. 头像截取 图片上传 js插件
  2. 【CSS】凹槽的写法
  3. perl6中函数参数(2)
  4. java===java基础学习(2)---运算符,三元操作符,数学函数
  5. Win10打开照片提示“无效的注册表值”解决方法
  6. python内建方法
  7. FineReport——JS二次开发(自定义翻页按钮)
  8. 我的新博客地址http://xxxbw.github.io/
  9. ORACLE中函数MONTHS_BETWEEN的使用
  10. 半透明AlphaBlend