P1231 教辅的组成

这个题一看便知是网络流量,(三分图??滑稽..)

就一个小细节,如果我们仅仅将所有的点分成三部分跑网络流的话会有点小问题..

因为这可能导致一本书被重复利用,就是有两条流经过同一本书,这样的话,我们就要通过限流的手段使得流经每本书的流只能是一.

我们将每本书拆成两个,再在两个点之间连一条1的边即可...

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=40010,INF=1e9;
int link[N],tot=1,n1,n2,n3,s,t,d[N],current[N],m1,m2;
struct edge{int y,v,next;}a[N*1000];
inline int read()
{
int x=0,ff=1;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*ff;
}
inline void add(int x,int y,int v)
{
a[++tot].y=y;a[tot].v=v;a[tot].next=link[x];link[x]=tot;
a[++tot].y=x;a[tot].v=0;a[tot].next=link[y];link[y]=tot;
}
inline bool bfs()
{
queue<int>q;q.push(s);
memset(d,0,sizeof(d));
memcpy(current,link,sizeof(current));
d[s]=1;
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=link[x];i;i=a[i].next)
{
int y=a[i].y;
if(d[y]||!a[i].v) continue;
d[y]=d[x]+1;
q.push(y);
if(y==t) return true;
}
}
return false;
}
inline int dinic(int x,int flow)
{
if(x==t) return flow;
int rest=flow,k;
for(int i=current[x];i&&rest;i=a[i].next)
{
current[x]=i;
int y=a[i].y;
if(d[y]==d[x]+1&&a[i].v)
{
k=dinic(y,min(rest,a[i].v));
if(!k) d[y]=0;
a[i].v-=k;
a[i^1].v+=k;
rest-=k;
}
}
return flow-rest;
}
int main()
{
freopen("1.in","r",stdin);
n1=read();n2=read();n3=read();
//书:1 - 2*n1,练习册:2*n1+1 - 2*n1+n2,答案:2*n1+n2+1 - 2*n1+n2+n3.
s=0;t=n1*2+n2+n3+1;
m1=read();
for(int i=1;i<=m1;++i)
{
int x=read(),y=read();
add(y+n1*2,x,1);
}
m2=read();
for(int i=1;i<=m2;++i)
{
int x=read(),y=read();
add(x+n1,y+n1*2+n2,1);
}
for(int i=1;i<=n1;++i) add(i,i+n1,1);
for(int i=1;i<=n2;++i) add(s,n1*2+i,1);
for(int i=1;i<=n3;++i) add(n1*2+n2+i,t,1);
int maxflow=0,flow;
while(bfs())
while(flow=dinic(s,INF)) maxflow+=flow;
printf("%d",maxflow);
return 0;
}

最新文章

  1. mybatis+oracle添加一条数据并返回所添加数据的主键问题
  2. 5.Android之image控件学习
  3. iOS 中NSOperationQueue,Grand Central Dispatch , Thread的上下关系和区别
  4. UNIX 网络编程第三版
  5. JavaScript基础精华02(函数声明,arguments对象,匿名函数,JS面向对象基础)
  6. loadrunner http协议put模式脚本编写
  7. decimall类型数据
  8. bzoj 1188 [HNOI2007]分裂游戏(SG函数,博弈)
  9. SGU 134.Centroid(图心)
  10. linux下执行sh文件报错:oswatcher_restart.sh: line 13: ./startOSW.sh: Permission denied
  11. JVM内存结构、垃圾回收那点事(转)
  12. Echarts自适应浏览器大小
  13. 【zabbix教程系列】三、zabbix 3.4 在centos 7 上安装详细步骤
  14. [iOS]多线程和GCD
  15. 数位dp小练
  16. windows7系统下配置开发环境 python2.7+pyqt4+pycharm
  17. ThinkingInJava 学习 之 0000001 一切都是对象
  18. H3 android 系统编译
  19. 诡异的DataTime.Now.ToString()
  20. EXCEL保存提示“隐私问题警告:此文档中包含宏……”解决办法

热门文章

  1. CodeForce-807C Success Rate(二分数学)
  2. PHP的OpenSSL加密扩展学习(三):证书操作
  3. Jmeter系列(12)- 上传接口压测
  4. win10连接mysql提示:ERROR 1045 (28000): Access denied for user &#39;root&#39;@&#39;localhost&#39; (using password: YES)
  5. lua自写限制并发访问模块
  6. django 模版-标签-视图-csrf-token-模版继承-HTML过滤器
  7. 定要过python二级 第10套
  8. AT2368-[AGC013B]Hamiltonish Path【构造】
  9. 华为云计算IE面试笔记-请描述华为容灾解决方案全景图,并解释双活数据中心需要从哪些角度着手考虑双活设计
  10. Maven----将手动下载的jar包以命令行的方式安装到本地MavenRepository中