题目链接

  妈耶

  我的图建反了两次    准确的说是有两个地方建反了,然后反上加反改了一个小时……

  知道为什么要拆点吗?

  

  假设这是你的图   左边到右边依次是超级源点    练习册     书     答案     超级汇点

  请问这张图的最大流是多少?

  如果把中间拆成这样:

  

  Book-in是跟练习册匹配的书的入端,Book-out是跟答案匹配的书的出端。相当于每本书都是一条隧道,有入口有出口,每本书的入口和对应的出口连边。

  请问现在这张图的最大流是多少?

  所以你看。

  代码放上:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype> inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} struct Edge{
int next,to,val;
}edge[];
int head[],num=-;
inline void add(int from,int to,int val){
edge[++num]=(Edge){ head[from],to,val};
head[from]=num;
} bool vis[];
int dfn[];
int list[];
int f[],h,t=;
int n,m,Start,End; bool bfs(){
memset(vis,,sizeof(vis));
f[]=Start;vis[Start]=;dfn[Start]=;h=;t=;
while(h++<t){
int from=f[h];
for(int i=head[from];i!=-;i=edge[i].next){
int to=edge[i].to;
if(vis[to]||(!edge[i].val)) continue;
dfn[to]=dfn[from]+;
vis[to]=;
f[++t]=to;
}
}
return vis[End];
} int dfs(int x,int val){
if(x==End||val==) return val;
int flow=;
vis[x]=;
for(int &i=list[x];i!=-;i=edge[i].next){
int to=edge[i].to;
if(dfn[to]==dfn[x]+&&!vis[to]&&edge[i].val>){
int now=dfs(to,std::min(edge[i].val,val));
if(now>){
edge[i].val-=now;
edge[i^].val+=now;
flow+=now;val-=now;
if(val<=) break;
}
}
}
if(flow!=val) dfn[x]=-;
return flow;
} int ans; int main(){
memset(head,-,sizeof(head));
int n1=read(),n2=read(),n3=read();
int n=n1*+n2;int N=n+n3;End=N+;
int m1=read();
for(int i=;i<=m1;++i){
int book=read(),note=read();
add(note+n1*,book,);
add(book,note+n1*,);
}
int m2=read();
for(int i=;i<=m2;++i){
int book=read(),ansnote=read();
add(book+n1,ansnote+n,);
add(ansnote+n,book+n1,);
}
for(int i=;i<=n1;++i){
add(i,i+n1,);
add(i+n1,i,);
}
for(int i=;i<=n2;++i){
add(Start,i+n1*,);
add(i+n1*,Start,);
}
for(int i=;i<=n3;++i){
add(i+n,End,);
add(End,i+n,);
}
while(bfs()){
memset(vis,,sizeof(vis));
for(int i=;i<=End;++i) list[i]=head[i];
int now=dfs(Start,0x7fffffff);
if(!now) break;
ans+=now;
}
printf("%d",ans);
return ;
}

  话说当前弧优化真好用

最新文章

  1. [MySQL]索引类型总结和使用技巧以及注意事项
  2. Qt中2D绘图问题总结(二)----------坐标系统
  3. svn/git的diff、patch
  4. 几种I/O模型功能和性能对比
  5. Update UI from an asynchronous thread
  6. Linux MD5值递归比对目录中的文件是否有修改
  7. 获取客户端的IP地址
  8. javascript中数组的迭代等操作
  9. Android5.0之NavigationView的使用
  10. jQuery图片延迟加载插件
  11. Akka(41): Http:DBTable-rows streaming - 数据库表行交换
  12. Node.js系列-http
  13. UNICODE与ASCII
  14. JSONModel(I)
  15. Docker Dockerfile 一
  16. java List集合记录 ArrayList和LinkedList的区别
  17. scrapy 报错 no module named win32api 的解决方案
  18. 《Science》:对年轻科学家的忠告
  19. ng-src 的坑
  20. 《构建高性能 Web站点》笔记

热门文章

  1. Obj-C Memory Management
  2. 最常见的 5 个导致节点重新启动、驱逐或 CRS 意外重启的问题 (文档 ID 1524455.1)
  3. 集成iAd广告
  4. video 的使用
  5. 爬虫学习之pdf读取和存储
  6. asp.net core vs2017运行控制台应用程序一闪而过没执行
  7. shell脚本,100以内的质数有哪些?
  8. Spring框架针对dao层的jdbcTemplate操作crud之query查询数据操作
  9. 初涉KMP算法
  10. 搭建pip源