[POJ-3281]

思路:

  把牛拆点;

  s向食物连边,流量1;

  饮料向t连边,流量1;

  食物向牛1连边,流量1;

  牛2向饮料连边,流量1;

  最大流;

来,上代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 2005
#define INF 0x7fffffff int n,f,d,s,t,head[maxn],E[maxn<<],V[maxn<<],F[maxn<<];
int cnt=,deep[maxn],que[maxn<<]; inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'') Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
} inline void edge_add(int u,int v,int f)
{
E[++cnt]=head[u],V[cnt]=v,F[cnt]=f,head[u]=cnt;
E[++cnt]=head[v],V[cnt]=u,F[cnt]=,head[v]=cnt;
} inline bool bfs()
{
for(int i=s;i<=t;i++) deep[i]=-;
int h=,tail=;deep[s]=,que[h]=s;
while(h<tail)
{
int now=que[h++];
for(int i=head[now];i;i=E[i])
{
if(deep[V[i]]<&&F[i]>)
{
deep[V[i]]=deep[now]+;
if(V[i]==t) return true;
que[tail++]=V[i];
}
}
}
return false;
} int flowing(int now,int flow)
{
if(flow<=||now==t) return flow;
int oldflow=;
for(int i=head[now];i;i=E[i])
{
if(F[i]>&&deep[V[i]]==deep[now]+)
{
int pos=flowing(V[i],min(flow,F[i]));
flow-=pos,oldflow+=pos,F[i]-=pos,F[i^]+=pos;
if(flow==) return oldflow;
}
}
if(oldflow==) deep[now]=-;
return oldflow;
} int main()
{
in(n),in(f),in(d);
int u,v,nf,nd;t=f+n+n+d+;
for(int i=;i<=f;i++) edge_add(s,i,);
for(int i=;i<=d;i++) edge_add(f+n+n+i,t,);
for(int i=;i<=n;i++)
{
edge_add(f+i,f+n+i,),in(nf),in(nd);
for(int j=;j<=nf;j++) in(u),edge_add(u,f+i,);
for(int j=;j<=nd;j++) in(u),edge_add(f+n+i,f+n+n+u,);
}
int ans=;
while(bfs()) ans+=flowing(s,INF);
cout<<ans;
return ;
}

最新文章

  1. 工厂模式模拟Spring的bean加载过程
  2. 动力节点Java培训告诉你Java线程的多功能用法
  3. Atitit截屏功能的设计解决方案
  4. 【leetcode】Surrounded Regions(middle)☆
  5. CSS实现垂直水平居中
  6. Injection Attacks-Log 注入
  7. JS跨域笔记
  8. 使用CocoaPods遇到的几个坑,记录一下
  9. Pthon MySQLdb 的安装
  10. Elasticsearch文档查询
  11. Ext JS 6应用程序Build后出现“c is not a constructor return new c(a[0])”的处理
  12. c/c++ linux epoll系列2 利用epoll_wait查看是否可以送信
  13. python 的xlrd模块
  14. 关于阿里云Centos服务器搭建Java网站不能访问的问题
  15. (1)MySQL(入门操作安装\基本指令)
  16. jenkins 图文教程 下载 --》安装--》更改默认端口号,附自启动脚本
  17. Executor框架(七)Future 接口、FutureTask类
  18. Oracle体系结构一(学习笔记)
  19. Flink本地环境安装部署
  20. 20155234 实验三 敏捷开发与XP实践

热门文章

  1. Eclipse 窗口说明---Eclipse教程第03课
  2. Win10安装bash慢的解决方案
  3. android压力测试monkey简单使用
  4. jmeter之录制控制器与代理的使用
  5. 3dMax,Maya与FBX
  6. 原始套接字--arp相关
  7. Linux特殊权限位
  8. Python 的音乐库
  9. Ajax---概念介绍
  10. MPLAB设置路径