wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

bzoj3829 POI2014 FAR-FarmCraft

题目链接思路用\(f[i]\)表示完成第\(i\)棵子树所需要得时间。考虑如果有两个子树\(a\)和\(b\),如果先去完成子树\(a\)，那么对于花费得时间就是\(f[b] + siz[a] \times 2 + 1\) 所以如果有先遍历\(a\)更优秀的话。那么一定有\(f[b] + ...

贪心

2019-02-13

0 524

bzoj2007 NOI2010 海拔(对偶图)

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

对偶图

2019-02-12

1 560

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

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

欧拉回路

2019-02-10

0 516

有源汇上下界网络流

有源汇上下界最大流例题 loj116 给出一个有源汇点的有向图。每条边有最大流量和最小流量。现在需要求出从源点到汇点的最大流可以是多少。前置知识上下界可行流思路先回顾有源汇上下界可行流干了些什么。其实可行流就是找到了一种满足流量下界的方...

2019-02-10

0 547

上下界可行流

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

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