ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共17篇）

P3386 【模板】二分图匹配 -网络流版

　　　　　　　　　　　　二分图匹配题目背景二分图感谢@一扶苏一提供的hack数据题目描述给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数输入输出格式输入格式：第一行，n,m,e 第二至e+1行，每行两个正整数u,v，表示u,v有一条连边 ...

网络流

2018-07-05

0 358

网络流二十四题飞行员配对方案问题

P2756 飞行员配对方案问题题目背景第二次世界大战时期.. 题目描述英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干...

网络流

2018-07-06

1 491

网络流二十四题分配问题

分配问题题目描述有 nn 件工作要分配给 nn 个人做。第 ii 个人做第 jj 件工作产生的效益为 c_{ij}cij 。试设计一个将 nn 件工作分配给 nn 个人做的分配方案，使产生的总效益最大。输入输出格式输入格式：文件的第 11 行有 11 个正整数 nn ，表...

网络流

2018-07-05

0 559

P4013 数字梯形问题网络流二十四题

P4013 数字梯形问题题目描述给定一个由 nn 行数字组成的数字梯形如下图所示。梯形的第一行有 m 个数字。从梯形的顶部的 m 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。分别遵守以下规则：从梯形...

网络流

2018-07-19

1 462

P2472 [SCOI2007]蜥蜴（网络最大流）

P2472 [SCOI2007]蜥蜴题目描述在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，...

网络流

2018-07-23

0 429

luogu 1004 方格取数

题目描述设有 $N \times N$ 的方格图 $(N \le 9)$ ，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 $0$ 。如下图所示（见样例）: A 0 0 0 0 0 0 0 0 0 0 13 0 0 6 0 0 0 0 0 0 ...

网络流

2018-08-07

1 438

网络流24题 P2754 [CTSC1999]家园

思路如图,建立分层图跑dinic 每次在残余网络里加边继续跑跑到ans>=k时候的i就是答案诶呀啊，忘记弄箭头了，最后一列是向上的箭头，不过聪明的你们应该没啥影响代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(i...

网络流最大流

2018-12-27

0 519

bzoj1741 [Usaco2005 nov]Asteroids 穿越小行星群最小点覆盖

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1741 思路消除所有的小行星每个点(x,y)只有选择x或者y才能被覆盖二分图最小点覆盖=最大流首先，最小顶点覆盖一定>=最大匹配，因为假设最大匹配为n，那么我们就得到...

网络流最小点覆盖

2019-02-18

0 524

4819: [Sdoi2017]新生舞会分数规划

题目 https://www.lydsy.com/JudgeOnline/problem.php?id=4819 思路分数规划的模板题？(好菜呀) 假如n=3吧(懒得写很长的式子) \(c=\frac{a_1+a_2+a_3}{b_1+b_2+b_3}\) 我们先二分一下，变为判定性问题 c...

网络流二分答案分数规划

2019-02-16

0 561

bzoj 1735: [Usaco2005 jan]Muddy Fields 泥泞的牧场最小点覆盖

链接 1735: [Usaco2005 jan]Muddy Fields 泥泞的牧场思路这就是个上一篇的稍微麻烦版(是变脸版，其实没麻烦) 用边长为1的模板覆盖地图上的没有长草的土地，不能覆盖草地每个点(x,y)只有选择x或者y才能被覆盖还是最小点覆盖，证明在上一篇横边和竖边得遍历一...

网络流最小点覆盖

2019-02-18

0 631