bzoj 1711 Dining吃饭 —— 最大流
2024-08-29 13:30:27
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1711
食物一列,牛拆点,饮料一列。
代码如下:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int const xn=,xm=6e4+,inf=1e9;
int n,F,D,S,T,hd[xn],ct=,nxt[xm],to[xm],c[xm],dis[xn],cur[xn];
queue<int>q;
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
void ade(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; c[ct]=z;}
void add(int x,int y,int z){ade(x,y,z); ade(y,x,);}
int id(int x,int t)//F,n1,n2,D
{if(t==)return x; if(t==)return F+x; if(t==)return F+n+x; if(t==)return F+n+n+x;}
bool bfs()
{
memset(dis,,sizeof dis);
dis[S]=; q.push(S);
while(q.size())
{
int x=q.front(); q.pop();
for(int i=hd[x],u;i;i=nxt[i])
if(!dis[u=to[i]]&&c[i])dis[u]=dis[x]+,q.push(u);
}
return dis[T];
}
int dfs(int x,int fl)
{
if(x==T)return fl;
int ret=;
for(int &i=cur[x],u;i;i=nxt[i])
{
if(dis[u=to[i]]!=dis[x]+||!c[i])continue;
int tmp=dfs(u,min(fl-ret,c[i]));
if(!tmp)dis[u]=;
c[i]-=tmp; c[i^]+=tmp;
ret+=tmp; if(ret==fl)break;
}
return ret;
}
int main()
{
n=rd(),F=rd(),D=rd(); S=; T=(n<<)+F+D+;
for(int i=;i<=F;i++)add(S,id(i,),);
for(int i=;i<=D;i++)add(id(i,),T,);
for(int i=;i<=n;i++)add(id(i,),id(i,),);
for(int i=,f,d,x;i<=n;i++)
{
f=rd(); d=rd();
for(int j=;j<=f;j++)x=rd(),add(id(x,),id(i,),);
for(int j=;j<=d;j++)x=rd(),add(id(i,),id(x,),);
}
int ans=;
while(bfs())
{
memcpy(cur,hd,sizeof hd);
ans+=dfs(S,inf);
}
printf("%d\n",ans);
return ;
}
最新文章
- Python的闭包
- c#调用C++DLL参数对应
- Mac废纸篓 不能完全清空的有效解决方法
- 模块";xxxx.dll";已加载,但对DllRegisterServer的调用失败,错误代码为 XXXXXXXXX
- bzoj 2002 LCT
- QTP之web常用对象
- mongodb c++ driver(2.53)windows编译
- Lua包管理工具Luarocks详解 - 15134559390的个人空间 - 开源中国社区
- KVO - 键值观察
- 自定义图文混排视图MyImageTextView
- HUD 2089 位数dp
- Android StrictMode介绍
- C++编程练习(4)----“实现简单的栈的链式存储结构“
- tmux进阶之tmuxinator
- Saslauthd服务实现SMTP发信认证
- Unity安卓打包遇到的问题。
- C语言典型编程3
- Java RMI的轻量级实现 - LipeRMI
- centos7如何查找文件?
- nargin与varargin的用法
热门文章
- iOS 蓝牙开发之(CoreBlueTooth)
- 20179209《Linux内核原理与分析》第十一周作业
- 我的Android进阶之旅------>如何将Android源码导入Eclipse中来查看(非常实用)
- Alex 的 Hadoop 菜鸟教程: 第2课 hadoop 安装教程 (CentOS6 CDH分支 yum方式)
- JETSON TK1 ~ 刷机和克隆固件
- ubuntu配置jdk环境
- Linuxshell资料汇总
- [原创]java WEB学习笔记31:会话与状态管理 session机制 概述(定义,session机制,session的声明周期,保存session的方式,Session的创建与删除)
- [原创]java WEB学习笔记27:深入理解面向接口编程
- [原创]java WEB学习笔记12:一个简单的serlet连接数据库实验