wbysr-CSDN博客

还是很水的题。。。。#include#include#include#include#define MAX 200005#define rep(i,j,k) for(int i=j;i<=k;i++)using namespace std;int n,k,to[2*MAX],next[2*MAX],head[MAX],ask_to[2*MAX],ask_next[2*MAX],a

2014-04-01 16:16:01 646

原创 bsoj1375 tarjan离线求lca

模板题。。。不多说了很好理解#include#include#include#include#define MAX 200005#define rep(i,j,k) for(int i=j;i<=k;i++)using namespace std;int n,k,to[2*MAX],next[2*MAX],head[MAX],ask_to[2*MAX],ask_next[2*MA

2014-04-01 06:28:05 558

原创 bzoj1786

显然填的数是不降的。。。然后把-1都扣出来，f[i][j]表示前i个-1填j的逆序数然后分别对与每个点求出来他前面的比他大的和后面的比他小的数就可以了#include#include#include#include#define MAX 10009#define rep(i,j,k) for(int i=j;i<=k;i++)#define inf 0x7fffffff

2014-03-31 21:20:43 638

原创 Bzoj1266 Ahoi2006 上学路线

BZOJ1266 anoi2006本文详解了最短路图的定义和构造，同时利用最小割实现了解题

2014-03-31 18:12:52 1529

原创 dp+树状数组 bzoj1264 AHOI2006基因匹配

bzoj1264 AHOI2006基因匹配用树状数组维护区间前缀最大值优化LCS

2014-03-30 11:40:32 1117

原创离散化 anoi2005穿越磁场 bzoj1967

AHOI2005 bzoj1967离散化套最短路的经典应用

2014-03-29 21:58:48 1262

原创树形dp 基环树直径 bzoj1791 ioi2008island

这个题真的好麻烦啊。。。就是给一堆基环树然后求出他们的直径的和我们首先不考虑环，然后对于每个点求出他所能走到的最大深度，然后缩点，就成了一个面包圈一样的环了然后脱环成链直接用单调队列dp就可以了队列中维护dp的决策，由于决策是有单调性的。。。#include#include#include#include#include#define MAX

2014-03-27 21:24:41 2254

原创点分治 poj1741

楼教主的男人八题之一。。。。狂T了一天，最后以把x错打成i而结束了漫长的debug。。。。这个题是我的第一个树分治树分治其实就是分治思想在树上的应用，在这个题中具体点就是把一颗子树中的路径分别计算然后递归到子树中再经行下一步的计算直到子树只有一个点这个操作是基于点的所以叫点分治这个题要有一个基础就是poj1655求树的重心如果不会看这里

2014-03-26 21:47:13 844

原创树形dp求树的重心 poj1655

本来是为了写树分治才写这个题的没想到竟然浪费了好长时间狂wa不止原来前向星的数组要开两倍。。。第一次用前向星真是光荣牺牲了。。。dp很简单先DFS一次,求出以每个节点为根的子树的节点个数s[i].设f[i]表示去掉i后,余下的各个子树结点个数的最大值.f[i]=max(n-s[i],max{s[j]}). (j为i的儿子).然后输出f[i]最小的

2014-03-25 16:33:28 849

原创线段相交 poj2653

很水的题。。。最难的是输出格式利用了队列#include#include#include#include#include#include#define eps 1e-8#define rep(i,j,k) for(int i=j;i<=k;i++)using namespace std;int n;struct point{ double

2014-03-18 21:27:37 589

原创 poj3680 zkw费用流

真心给zkw大神跪了。。。这个算是模板题，不过构图显然不是我想出来的。。。。算是第一个费用流。。。以后要多写点网络流啊。。一开始我用vector存的边然后交上去竟然TLE！！！！！这简直就是对vector党的鄙视啊。。。然后没办法把vector注释掉换前向星了。。。看来以后只能用前向星存图了。。。#include#include#include#i

2014-03-13 19:12:37 940

原创 poj3469 DINIC模板(vector+前向星)

网络流DINIC模板 poj3469本文采用了vector和前向星两种不同的数据结构分别实现了朴素的dinic算法

2014-03-12 04:48:54 1331

原创 bzoj 1191 匈牙利算法二分图匹配

很水的题。。。用来复习二分图用的。。。。不过还剩点问题没有解决，这个留到明天#include#include#include#include#include#define pb push_back#define MAX 100010#define rep(x,y,z) for(int x=y;x<=z;x++)using namespace std;int n,m,m

2014-03-10 22:55:37 653

空空如也

空空如也