教辅的组成最大流

作者：JUN-围脖 | 来源：互联网 | 2023-09-13 13:44

题目背景滚粗了的HansBug在收拾旧语文书，然而他发现了什么奇妙的东西。题目描述蒟蒻HansBug在一本语文书里面发现了一本答案，然而他却明明记得这书

题目背景

滚粗了的HansBug在收拾旧语文书&＃xff0c;然而他发现了什么奇妙的东西。

题目描述

蒟蒻HansBug在一本语文书里面发现了一本答案&＃xff0c;然而他却明明记得这书应该还包含一份练习题。然而出现在他眼前的书多得数不胜数&＃xff0c;其中有书&＃xff0c;有答案&＃xff0c;有练习册。已知一个完整的书册均应该包含且仅包含一本书、一本练习册和一份答案&＃xff0c;然而现在全都乱做了一团。许多书上面的字迹都已经模糊了&＃xff0c;然而HansBug还是可以大致判断这是一本书还是练习册或答案&＃xff0c;并且能够大致知道一本书和答案以及一本书和练习册的对应关系&＃xff08;即仅仅知道某书和某答案、某书和某练习册有可能相对应&＃xff0c;除此以外的均不可能对应&＃xff09;。既然如此&＃xff0c;HansBug想知道在这样的情况下&＃xff0c;最多可能同时组合成多少个完整的书册。

输入输出格式

输入格式&＃xff1a;

第一行包含三个正整数N1、N2、N3&＃xff0c;分别表示书的个数、练习册的个数和答案的个数。

第二行包含一个正整数M1&＃xff0c;表示书和练习册可能的对应关系个数。

接下来M1行每行包含两个正整数x、y&＃xff0c;表示第x本书和第y本练习册可能对应。&＃xff08;1<&＃61;x<&＃61;N1&＃xff0c;1<&＃61;y<&＃61;N2&＃xff09;

第M1&＃43;3行包含一个正整数M2&＃xff0c;表述书和答案可能的对应关系个数。

接下来M2行每行包含两个正整数x、y&＃xff0c;表示第x本书和第y本答案可能对应。&＃xff08;1<&＃61;x<&＃61;N1&＃xff0c;1<&＃61;y<&＃61;N3&＃xff09;

输出格式&＃xff1a;

输出包含一个正整数&＃xff0c;表示最多可能组成完整书册的数目。

输入输出样例

输入样例#1&＃xff1a; 复制

5 3 4
5
4 3
2 2
5 2
5 1
5 3
5
1 3
3 1
2 2
3 3
4 3

输出样例#1&＃xff1a; 复制

说明

样例说明&＃xff1a;

如题&＃xff0c;N1&＃61;5&＃xff0c;N2&＃61;3&＃xff0c;N3&＃61;4&＃xff0c;表示书有5本、练习册有3本、答案有4本。

M1&＃61;5&＃xff0c;表示书和练习册共有5个可能的对应关系&＃xff0c;分别为&＃xff1a;书4和练习册3、书2和练习册2、书5和练习册2、书5和练习册1以及书5和练习册3。

M2&＃61;5&＃xff0c;表示数和答案共有5个可能的对应关系&＃xff0c;分别为&＃xff1a;书1和答案3、书3和答案1、书2和答案2、书3和答案3以及书4和答案3。

所以&＃xff0c;以上情况的话最多可以同时配成两个书册&＃xff0c;分别为&＃xff1a;书2&＃43;练习册2&＃43;答案2、书4&＃43;练习册3&＃43;答案3。

数据规模&＃xff1a;

对于数据点1, 2, 3&＃xff0c;M1&＃xff0c;M2<&＃61; 20

对于数据点4~10&＃xff0c;M1&＃xff0c;M2 <&＃61; 20000

把书拆点&＃xff0c;然后跑一遍最大流

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include //#pragma GCC optimize(2) using namespace std; #define maxn 2000005 #define inf 0x7fffffff //#define INF 1e18 #define rdint(x) scanf("%d",&x) #define rdllt(x) scanf("%lld",&x) #define rdult(x) scanf("%lu",&x) #define rdlf(x) scanf("%lf",&x) #define rdstr(x) scanf("%s",x) typedef long long ll; typedef unsigned long long ull; typedef unsigned int U; #define ms(x) memset((x),0,sizeof(x)) const long long int mod &＃61; 1e9 &＃43; 7; #define Mod 1000000000 #define sq(x) (x)*(x) #define eps 1e-3 typedef pair pii; #define pi acos(-1.0) //const int N &＃61; 1005; #define REP(i,n) for(int i&＃61;0;i<(n);i&＃43;&＃43;) typedef pair pii; inline ll rd() {ll x &＃61; 0;char c &＃61; getchar();bool f &＃61; false;while (!isdigit(c)) {if (c &＃61;&＃61; &＃39;-&＃39;) f &＃61; true;c &＃61; getchar();}while (isdigit(c)) {x &＃61; (x <<1) &＃43; (x <<3) &＃43; (c ^ 48);c &＃61; getchar();}return f ? -x : x; }ll gcd(ll a, ll b) {return b &＃61;&＃61; 0 ? a : gcd(b, a%b); } int sqr(int x) { return x * x; }/*ll ans; ll exgcd(ll a, ll b, ll &x, ll &y) {if (!b) {x &＃61; 1; y &＃61; 0; return a;}ans &＃61; exgcd(b, a%b, x, y);ll t &＃61; x; x &＃61; y; y &＃61; t - a / b * y;return ans; } */ int n, m; int st, ed; struct node {int u, v, nxt, w; }edge[maxn]; int head[maxn]; int tot; void addedge(int u, int v, int w) {edge[tot].u &＃61; u; edge[tot].v &＃61; v; edge[tot].nxt &＃61; head[u];edge[tot].w &＃61; w; head[u] &＃61; tot&＃43;&＃43;; } int rk[maxn]; int bfs() {queueq; ms(rk); rk[st] &＃61; 1; q.push(st);while (!q.empty()) {int tmp &＃61; q.front(); q.pop();for (int i &＃61; head[tmp]; i !&＃61; -1; i &＃61; edge[i].nxt) {int to &＃61; edge[i].v;if (rk[to] || edge[i].w <&＃61; 0)continue;rk[to] &＃61; rk[tmp] &＃43; 1; q.push(to);}}return rk[ed]; } int dfs(int u, int flow) {if (u &＃61;&＃61; ed)return flow;int add &＃61; 0;for (int i &＃61; head[u]; i !&＃61; -1 && add } int ans; void dinic() {while (bfs())ans &＃43;&＃61; dfs(st, inf); }int N1, N2, N3;int main() {//ios::sync_with_stdio(0);memset(head, -1, sizeof(head));rdint(N1); rdint(N2); rdint(N3);int m1; rdint(m1);st &＃61; 2 * N1 &＃43; N2 &＃43; N3 &＃43; 3; ed &＃61; st &＃43; 1;while (m1--) {int x, y;rdint(x); rdint(y);addedge(y, x &＃43; N2, 1); addedge(x &＃43; N2, y, 0);// addedge(st, y, 1); addedge(y, st, 0);}int m2; rdint(m2);while (m2--) {int x, y; rdint(x); rdint(y);addedge(x &＃43; N1 &＃43; N2, y &＃43; N1 * 2 &＃43; N2, 1); addedge(y &＃43; 2 * N1 &＃43; N2, x &＃43; N1 &＃43; N2, 0);// addedge(y &＃43; 2 * N1 &＃43; N2, ed, 1); addedge(ed, 2 * N1 &＃43; N2 &＃43; y, 0);}for (int i &＃61; 1; i <&＃61; N1; i&＃43;&＃43;) {addedge(i &＃43; N2, i &＃43; N2 &＃43; N1, 1); addedge(i &＃43; N2 &＃43; N1, i &＃43; N2, 0);}for (int i &＃61; 1; i <&＃61; N2; i&＃43;&＃43;)addedge(st, i, 1), addedge(i, st, 0);for (int i &＃61; 1; i <&＃61; N3; i&＃43;&＃43;)addedge(i &＃43; 2 * N1 &＃43; N2, ed, 1), addedge(ed, i &＃43; 2 * N1 &＃43; N2, 0);dinic();cout <}

dinic&＃xff1b;

转:https://www.cnblogs.com/zxyqzy/p/10267903.html

推荐阅读

go
AOJ.863 分配书籍问题（深度优先搜索算法）

题目解析给定 n 个人和 n 种书籍，每个人都有一个包含自己喜好的书籍列表。目标是计算出满足以下条件的分配方案数量：1. 每个人都必须获得他们喜欢的书籍；2. 每本书只能分配给一个人。通过使用深度优先搜索算法，可以系统地探索所有可能的分配组合，确保每个分配方案都符合上述条件。该方法能够有效地处理这类组合优化问题，找到所有可行的解。 ... [详细]

蜡笔小新 2024-11-09 20:10:25
go
C++ 从文件中逐行读取结构体数据，并将其存储到向量中，最终输出至控制台和新文件

在C++程序中，文档A的每一行包含一个结构体数据，其中某些字段可能包含不同数量的数字。需要将这些结构体数据逐行读取并存储到向量中，随后不仅在控制台上显示，还要输出到新创建的文档B中。希望得到指导，感谢！ ... [详细]

蜡笔小新 2024-11-09 18:40:33
go
C++ 异步编程中获取线程执行结果的方法与技巧及其在前端开发中的应用探讨

本文探讨了C++异步编程中获取线程执行结果的方法与技巧，并深入分析了这些技术在前端开发中的应用。通过对比不同的异步编程模型，本文详细介绍了如何高效地处理多线程任务，确保程序的稳定性和性能。同时，文章还结合实际案例，展示了这些方法在前端异步编程中的具体实现和优化策略。 ... [详细]

蜡笔小新 2024-11-09 15:14:28
input
2018 HDU 多校联合第五场 G题：Glad You Game（线段树优化解法）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6356在《Glad You Game》中，Steve 面临一个复杂的区间操作问题。该题可以通过线段树进行高效优化。具体来说，线段树能够快速处理区间更新和查询操作，从而大大提高了算法的效率。本文详细介绍了线段树的构建和维护方法，并给出了具体的代码实现，帮助读者更好地理解和应用这一数据结构。 ... [详细]

蜡笔小新 2024-11-08 19:17:23
go
在 QQmlPropertyMap 的派生类中无法调用槽函数或 Q_INVOKABLE 方法？

在尝试对 QQmlPropertyMap 类进行测试驱动开发时，发现其派生类中无法正常调用槽函数或 Q_INVOKABLE 方法。这可能是由于 QQmlPropertyMap 的内部实现机制导致的，需要进一步研究以找到解决方案。 ... [详细]

蜡笔小新 2024-11-11 15:34:22
function
使用 QT 实现 YUV420 图像渲染技术

在使用 Qt 进行 YUV420 图像渲染时，由于 Qt 本身不支持直接绘制 YUV 数据，因此需要借助 QOpenGLWidget 和 OpenGL 技术来实现。通过继承 QOpenGLWidget 类并重写其绘图方法，可以利用 GPU 的高效渲染能力，实现高质量的 YUV420 图像显示。此外，这种方法还能显著提高图像处理的性能和流畅性。 ... [详细]

蜡笔小新 2024-11-09 15:02:41
input
【BZOJ1012】[JSOI 2008] 最大数值问题：ST表优化解决方案

题目要求维护一个数列，并支持两种操作：一是查询操作，语法为QL，用于查询数列末尾L个数中的最大值；二是更新操作，用于修改数列中的某个元素。本文通过ST表（Sparse Table）优化查询效率，确保在O(1)时间内完成查询，同时保持较低的预处理时间复杂度。 ... [详细]

蜡笔小新 2024-11-09 12:14:17
function
ESP8266 01S Web 服务器成功启动：详细解决方案与实践指南

本文详细介绍了一种利用 ESP8266 01S 模块构建 Web 服务器的成功实践方案。通过具体的代码示例和详细的步骤说明，帮助读者快速掌握该模块的使用方法。在疫情期间，作者重新审视并研究了这一未被充分利用的模块，最终成功实现了 Web 服务器的功能。本文不仅提供了完整的代码实现，还涵盖了调试过程中遇到的常见问题及其解决方法，为初学者提供了宝贵的参考。 ... [详细]

蜡笔小新 2024-11-08 19:12:49
go
暑假强化训练：计算几何深度探索

经过两天的努力，终于成功解决了半平面交模板题POJ3335的问题。原来是在`OnLeft`函数中漏掉了关键的等于号。通过这次训练，不仅加深了对半平面交算法的理解，还提升了调试和代码实现的能力。未来将继续深入研究计算几何的其他核心问题，进一步巩固和拓展相关知识。 ... [详细]

蜡笔小新 2024-11-08 16:20:55
go
洛谷 P4035 [JSOI2008] 球形空间生成器（高斯消元法 / 模拟退火算法）

本文介绍了洛谷 P4035 [JSOI2008] 球形空间生成器问题的解决方案，主要使用了高斯消元法和模拟退火算法。通过这两种方法，可以高效地求解多维空间中的球心位置。文章提供了详细的算法模板和实现代码，适用于 ACM 竞赛和其他相关应用场景。数据范围限制在 10 以内，确保了算法的高效性和准确性。 ... [详细]

蜡笔小新 2024-11-08 13:55:00
input
利用 Node.js 和 Express（4.x 及以上版本）构建高效文件上传功能

本文介绍了如何使用 Node.js 和 Express（4.x 及以上版本）构建高效的文件上传功能。通过引入 `multer` 中间件，可以轻松实现文件上传。首先，需要通过 `npm install multer` 安装该中间件。接着，在 Express 应用中配置 `multer`，以处理多部分表单数据。本文详细讲解了 `multer` 的基本用法和高级配置，帮助开发者快速搭建稳定可靠的文件上传服务。 ... [详细]

蜡笔小新 2024-11-11 18:02:17
hook
C++实现的键盘输入记录程序源代码分析与应用

本文详细解析了使用C++实现的键盘输入记录程序的源代码，该程序在Windows应用程序开发中具有很高的实用价值。键盘记录功能不仅在远程控制软件中广泛应用，还为开发者提供了强大的调试和监控工具。通过具体实例，本文深入探讨了C++键盘记录程序的设计与实现，适合需要相关技术的开发者参考。 ... [详细]

蜡笔小新 2024-11-10 15:44:03
format
深入剖析Java中SimpleDateFormat在多线程环境下的潜在风险与解决方案

深入剖析Java中SimpleDateFormat在多线程环境下的潜在风险与解决方案 ... [详细]

蜡笔小新 2024-11-09 19:04:36
format
如何撰写适应变化的高效代码：策略与实践

编写高质量且适应变化的代码是每位程序员的追求。优质代码的关键在于其可维护性和可扩展性。本文将从面向对象编程的角度出发，探讨实现这一目标的具体策略与实践方法，帮助开发者提升代码效率和灵活性。 ... [详细]

蜡笔小新 2024-11-09 10:20:32
config
iOS中基于HTTPS协议的安全网络请求实现

在iOS开发中，基于HTTPS协议的安全网络请求实现至关重要。HTTPS（全称：HyperText Transfer Protocol over Secure Socket Layer）是一种旨在提供安全通信的HTTP扩展，通过SSL/TLS加密技术确保数据传输的安全性和隐私性。本文将详细介绍如何在iOS应用中实现安全的HTTPS网络请求，包括证书验证、SSL握手过程以及常见安全问题的解决方法。 ... [详细]

蜡笔小新 2024-11-08 17:13:51

JUN-围脖

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章