冒泡ioa
冒泡ioa

图论
文章归档

[SHOI2001]小狗散步(最大匹配)

题目链接 题解 把人走的点当作左部节点,🐕走的当作右部 对于每个人走的节点,如果他与下一个节点的距离的两倍大于某个从当前节点走到右部节点+右部节点走到下一节点的距离,即可连边 输出方案的话,注意到如果右部节点被匹配,match[i]就是匹配它的左部节点,存起来…

   226   2019-04-18   去围观

[ZJOI2007]矩阵游戏(最大匹配)

题目链接 题解 两眼题 考虑每一行,如果当前列为1,则行与列连边 于是我们左部是每一行,右部是列,可以发现,如果有解,当且仅当每一列都有行与之匹配 跑匈牙利即可 代码 [crayon-6094c1e6f3bb1351995328/]

   227   2019-04-18   去围观

[CF1139E]Maximize Mex(二分图最大匹配)

题目链接 题目大意 有 $n$ 个学生 $m$ 个社团,每个学生有一个能力值 $p_i$ 属于 $c_i$ 社团,接下来的 $d$ 天里,每天由校长钦点一个学生滚蛋,然后由你从每个社团选一个人(没人就不选),对于每天,求这些人 $p_i$ 的 $mex$ 的最大值 $mex$ 即为序列中最小的非…

   209   2019-04-17   去围观

[UVA1660]电视网络Cable TV Network

题目链接 不得不说,网络流的题目其实实现起来都是套模板,但是要想到就很困难。 很多人学了最小割之后就来切这道“裸题”,数据范围小,还没要求输出具体方案,太简单了! 但是最小割是适用于有向图,而且是边集,但是这道题是要我们找出点的个数,而且是无向图。 …

   632   2019-01-22   去围观

[sdut1808]安全网络问题

题面 只能看看题面,数据是错的。 就是求一张图的所有点双连通分量,将它们内部排序再外部排序数出来,关于点双连通分量没什么好讲的,网上各种博客都写烂了。还是直接上代码吧。 [crayon-6094c1e6f41be042720711/]

   331   2018-11-06   去围观

[APIO2010]巡逻

题目描述 在一个地区中有 n 个村庄,编号为 1, 2, ..., n。有 n – 1 条道路连接着这些村 庄,每条道路刚好连接两个村庄,从任何一个村庄,都可以通过这些道路到达其 他任一个村庄。每条道路的长度均为 1 个单位。 为保证该地区的安全,巡警车每天要到所有的道路上巡逻…

   245   2018-10-25   去围观

[P1979][NOIP2013]华容道

样例输入 [crayon-6094c1e70046e600057548/] 样例输出 [crayon-6094c1e700474261716379/] 题解 算法分析摘自《2013全国信息学奥林匹克年鉴》 算法分析 这道题主要考察同学们对最短路算法的理解。(我考试的时候怎么没看出来orz) 本题是一个很典型的最…

   258   2018-10-16   去围观

[洛谷P1967][NOIP2013]货车运输

题目 题目描述 A国有n座城市,编号从1到n,城市之间有m条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有q 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。 输入输出格式 输入格式: 第一行有两个用一个空格隔开…

   246   2018-10-11   去围观

[NOIP2014]联合权值

题目 题目描述 无向连通图G 有n 个点,n – 1 条边。点从1 到n 依次编号,编号为 i 的点的权值为W i ,每条边的长度均为1 。图上两点( u , v ) 的距离定义为u 点到v 点的最短距离。对于图G 上的点对( u, v) ,若它们的距离为2 ,则它们之间会产生Wu ×Wv 的联合权值…

   183   2018-10-01   去围观

[NOIP2009]最优贸易

题目 题目描述 C 国有n 个大城市和m 条道路,每条道路连接这n 个城市中的某两个城市。任意两个 城市之间最多只有一条道路直接相连。这m 条道路中有一部分为单向通行的道路,一部分 为双向通行的道路,双向通行的道路在统计条数时也计为1 条。 C 国幅员辽阔,各地…

   209   2018-10-01   去围观
加载更多