wxyww

未归档

精品(28) 题解(65)

/ 注册

全部文章 / 未归档（共302篇）

bzoj2007 NOI2010 海拔(对偶图)

80分(最小割)思路先考虑如果没有题目中东南角为\(1\)那个限制的话会怎样。那么只要让每个点的海拔都是\(0\)就行了。这样不论怎样走，最后的答案都是0. 然后再考虑那个东南角为\(1\)的限制表达了什么。其实说明了最后的答案一定是右下角一部分海拔全部为\(1\)，左上角一部分海拔全部为\(...

对偶图

2019-02-12

1 560

poj1637 Sightseeing tour(混合图欧拉回路)

题目链接题意给出一个混合图(有无向边，也有有向边)，问能否通过确定无向边的方向，使得该图形成欧拉回路。思路这是一道混合图欧拉回路的模板题。一张图要满足有欧拉回路，必须满足每个点的度数为偶数。对于这道题，我们先随便给无向边定个向。这时能够形成欧拉回路的必须条件就是每个点的入度和出度...

欧拉回路

2019-02-10

0 516

上下界可行流

无源汇上下界可行流题目给出一个有向图。每条边有流量上界和下界，问是否存在一中流量分配方案，使得每个点流量守恒(即流入量=流出量) 思路解决这种问题的主体思路就是在初始流的基础上不断添加流量，使得满足流量守恒。初始流很显然应该是每条边流量的下界。但是这样并不满足流量守恒。然...

2019-02-10

0 466

bzoj2400 Spoj 839 Optimal Marks

题目链接思路既然是异或预算，很容易想到按位操作。按位操作之后，每个点的权值就只有\(0\)和\(1\)两个了，然后从\(S\)向所有权值为\(0\)的点连一条\(INF\)的边，从所有权值为\(1\)的点向\(T\)连一条\(INF\)的边。然后将原图中的边全都连成权值为\(1\)的边。然...

2019-02-10

0 407

01分数规划

问题 \(01\)分数规划是用来解决这样一类问题有\(n\)个物品，每个物品都有一个属性\(p\)和\(w\)。要从中选出\(K\)个物品使得\(\frac{\sum\limits_{i=1}^Kp_i}{\sum\limits_{i=1}^Kw_i}\)最大，输出最大值。要求是个分数 ...

分数规划

2019-02-09

0 513

bzoj1565 植物大战僵尸

题目链接思路如果想消灭掉一个植物，那么必须先消灭掉左右能保护这个植物的植物。这就成了最大权闭合子图的模板题了。有两个需要注意的地方。第一个就是，能保护当前植物的植物还有当前植物右面的所有植物。第二个就是，在环里的植物或者是被在环里的植物所保护的植物是无法消灭的。所以先拓扑一下，找出所...

拓扑排序

2019-02-08

0 493

bzoj3144 切糕

题目链接题意这个题首先要理解好题意，就是说给这个长方体横着切开。要求相邻的两个位置切点的为值不能相差大于\(D\)。说的再直白一点就是。有一个\(P\times Q\)的矩阵，要在这\(P \times Q\)个格子里填区间\([1,R]\)中的数字。位置为\((x,y)\)的格子填\(z...

2019-02-08

0 541

loj6045 价

题目链接思路从源点\(S\)向每种药连一条边权为\(-p+inf\)的边。从每种药向他所需要的药材连一条边权为\(INF\)的边。从每种药材向汇点\(T\)连一条边权为\(inf\)的边。 \(INF>inf\) 用最小割减去源点连向药材的边权之和。代码 #include<...

2019-02-08

0 437

bzoj3894 文理分科

题目链接思路先将题目转化为求最小割。也就是要找出一些贡献不选，使得这些贡献的和最小。对于单个点的贡献。显然我们可以从\(S\)到这个点连一条容量为选文收益的边。从这个点到\(T\)连一条容量为选理收益的边。然后考虑哪些额外的贡献。只要相邻的这\(5\)个点中有任何一个不选文，那么这个集合...

2019-02-07

0 588

luogu3731 新型城市化

题目链接思路这道题对于题意的转化很关键。题目要求的是添上一条边，使得图中最大团的大小变大。给出的边是原图的补集，这就给我们了提示。因为题目中说，原图中最多有两个团。所以给出的边一定形成了一个二分图。那么最大团就是新图中的最大独立集。那么问题就转化成了，在新图中删除一条边，使得新图中的...

二分图 tarjan

2019-02-07

0 458