P1231 教辅的组成(最大流)
2024-09-07 00:34:47
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;
}
最新文章
- mybatis+oracle添加一条数据并返回所添加数据的主键问题
- 5.Android之image控件学习
- iOS 中NSOperationQueue,Grand Central Dispatch , Thread的上下关系和区别
- UNIX 网络编程第三版
- JavaScript基础精华02(函数声明,arguments对象,匿名函数,JS面向对象基础)
- loadrunner http协议put模式脚本编写
- decimall类型数据
- bzoj 1188 [HNOI2007]分裂游戏(SG函数,博弈)
- SGU 134.Centroid(图心)
- linux下执行sh文件报错:oswatcher_restart.sh: line 13: ./startOSW.sh: Permission denied
- JVM内存结构、垃圾回收那点事(转)
- Echarts自适应浏览器大小
- 【zabbix教程系列】三、zabbix 3.4 在centos 7 上安装详细步骤
- [iOS]多线程和GCD
- 数位dp小练
- windows7系统下配置开发环境 python2.7+pyqt4+pycharm
- ThinkingInJava 学习 之 0000001 一切都是对象
- H3 android 系统编译
- 诡异的DataTime.Now.ToString()
- EXCEL保存提示“隐私问题警告:此文档中包含宏……”解决办法
热门文章
- CodeForce-807C Success Rate(二分数学)
- PHP的OpenSSL加密扩展学习(三):证书操作
- Jmeter系列(12)- 上传接口压测
- win10连接mysql提示:ERROR 1045 (28000): Access denied for user &#39;root&#39;@&#39;localhost&#39; (using password: YES)
- lua自写限制并发访问模块
- django 模版-标签-视图-csrf-token-模版继承-HTML过滤器
- 定要过python二级 第10套
- AT2368-[AGC013B]Hamiltonish Path【构造】
- 华为云计算IE面试笔记-请描述华为容灾解决方案全景图,并解释双活数据中心需要从哪些角度着手考虑双活设计
- Maven----将手动下载的jar包以命令行的方式安装到本地MavenRepository中