题目描述

/*
s->练习册(1~b)->书(b+1~a+b)->答案(a+b+1~a+b+c)->t
但是可能会有多本练习册指向同一本书,这本书又可能会指向多本答案
这样每本书对答案的贡献就不只是1了,所以考虑对书进行拆点
s->练习册(1~b)->书(b+1~a+b)->(a+b+a~a+a+b)->答案(a+a+b+1~a+a+b+c)->t
*/
#include<iostream>
#include<cstdio>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e5+;
struct node{
int v,f,nxt;
}e[N*];
int m,a,b,c,Enum=,ans,t;
int front[N],cur[N],deep[N];
int q[N];
int qread()
{
int x=;
char ch=getchar();
while(ch<'' || ch>'')ch=getchar();
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x;
}
void Insert(int u,int v)
{
e[++Enum].v=v;
e[Enum].f=;
e[Enum].nxt=front[u];
front[u]=Enum;
e[++Enum].v=u;
e[Enum].nxt=front[v];
front[v]=Enum;
}
bool bfs()
{
for(int i=;i<=t;i++)
{
deep[i]=;
cur[i]=front[i];
}
int head=,tail=;
deep[]=;
q[++tail]=;
int u;
while(head<=tail)
{
u=q[head++];
for(int i=front[u];i;i=e[i].nxt)
if(e[i].f && !deep[e[i].v])
{
deep[e[i].v]=deep[u]+;
if(e[i].v==t)
return ;
q[++tail]=e[i].v;
}
}
return ;
}
int dfs(int now,int cur_flow)
{
if(now==t)return cur_flow;
int rest=cur_flow,v;
for(int &i=cur[now];i;i=e[i].nxt)
{
v=e[i].v;
if(e[i].f && deep[v]==deep[now]+ && rest)
{
int new_flow=dfs(v,min(e[i].f,rest));
e[i].f-=new_flow;
e[i^].f+=new_flow;
rest-=new_flow;
if(!rest)return cur_flow;
}
}
deep[now]=;
return cur_flow-rest;
}
void Dinic()
{
while(bfs())
ans+=dfs(,INF);
printf("%d\n",ans);
}
int main()
{
scanf("%d%d%d",&a,&b,&c);
t=a+a+b+c+;
for(int i=;i<=b;i++)
Insert(,i);
for(int i=;i<=a;i++)
Insert(i+b,i+a+b);
for(int i=;i<=c;i++)
Insert(i+a+a+b,t);
scanf("%d",&m);
int u,v;
for(int i=;i<=m;i++)
{
u=qread();v=qread();
Insert(v,u+b);
}
scanf("%d",&m);
for(int i=;i<=m;i++)
{
u=qread();v=qread();
Insert(u+a+b,v+a+a+b);
}
Dinic();
return ;
}

最新文章

  1. LYDSY模拟赛day2 Dash Speed
  2. java.lang.OutOfMemoryError处理错误
  3. 内存回收,Dispose,Close,Finalie(C#中的析构函数)
  4. [ActionScript 3.0] AS3 ConvolutionFilter卷积滤镜的应用
  5. echarts地图点定位的问题
  6. xshell + xmanger连接centos gnome+ kde桌面 for需要X window的App
  7. 更好的抽屉效果(ios)
  8. Geronimo tomcat: 在 Apache Geronimo 插件体系中将 Apache Tomcat 这个优秀的 Web 容器整合至其中
  9. EF生成模型出现异常:表“TableDetails“中列“IsPrimaryKey”的值为DBNull解决方法
  10. Nmon实时监控并生成HTML监控报告
  11. centos7.4安装npm
  12. Pandas分组级运算和转换
  13. python 多线程小方法
  14. openStack instance error 恢复
  15. Winform下判断文件和文件夹是否存在
  16. dp乱写3:环形区间dp(数字游戏)
  17. ios 字符串截取
  18. [C/C++] const用法详解
  19. codevs 1959 拔河比赛--判断背包内刚好装满n/2个物品
  20. hdu 1422(贪心)

热门文章

  1. Spring Cloud Stream如何消费自己生产的消息
  2. [LOJ2541] [PKUWC2018] 猎人杀
  3. 查询本地ip以及ip地址库查询
  4. JavaScript中匿名函数this指向问题
  5. 配置CTS+
  6. 一个时间O(n)的洗牌算法
  7. 【代码片段】定时记录CPU使用率并保存为CSV
  8. vscode编辑器自定义配置
  9. 编译安装php服务报错问题:configure: error: Cannot find libmysqlclient under /usr.
  10. visual studio 应用场景