图论

BZOJ2115 [Wc2011] Xor 线性基+DFS 图论

BZOJ2115 [Wc2011] Xor 线性基+DFS

题目   给出一个无向图,求一条1-n的路径,使路径边权xor和最大。 首先,可以把一条简单路径和任意多个环拼在一起,形成一条题目所求的路径。接着,对于任意一条简单路径,都可以和一些环的权值异或在一起,达到其他简单路径的效果。所以,我们只需找出任意一条简单路径,找到所有的环,再把环上的xo···
BZOJ2337 [HNOI2011]XOR和路径 高斯消元 图论

BZOJ2337 [HNOI2011]XOR和路径 高斯消元

题目链接 一遍填以前的坑,一遍翻达哥的题表,结果就做了一堆高斯消元= = 考虑到二进制上每一位都是独立的,我们可以按位分别计算概率。 还是倒着做,设f[i]:从i点到达n点,该二进制位异或和为1的概率。 当遇到一条二进制为1的边时,意味着通过这条边,按照定义,概率应该取对立面,所以f[i]=p[i]···
BZOJ2707 [SDOI2012]走迷宫 Tarjan+高斯消元 图论

BZOJ2707 [SDOI2012]走迷宫 Tarjan+高斯消元

  题目链接 和BZOJ3270比较相似,都是在图上高斯消元来转移状态。 观察数据范围,可以很明显地看出来必须先Tarjan缩点,之后在强连通分量里面进行高斯消元。 一开始仿照3270写了个正着推出的式子,发现不太好搞,于是重新倒着想了一遍。 设f[i]:从i点出发走到终点的期望步数,则f···
BZOJ1093 最大半连通子图 tarjan+最长链 图论

BZOJ1093 最大半连通子图 tarjan+最长链

画画图,可以看出来强连通分量里面的肯定都是,所以缩点去环,建新图。观察一下,可以发现一个半联通子图没法跨越两条链,就是说最大的联通子图在新图上一定是一条最长链,DFS一下就可以求出来。就是统计最长链数的时候一开始只想出了再DFS一次的做法,但因为无形中又加了一维所以光荣TLE。后来才发现,最长链数只···
Evensgn剪树枝(tree.*) 树形DP 图论

Evensgn剪树枝(tree.*) 树形DP

又是一道树形DP,考试打暴力期望60,然而只骗到了30。思路非常不显然,至今懵逼。设f[i][0]表示i点上方的连通块中不包含黑点,在i的子树中的方案数;f[i][1]相反。这样设计状态,可以考虑砍i点的父边。 设当前考虑的是u点,先不考虑u点的颜色,递归处理u的子树,递归完成后,再考虑f[u]的取···
BZOJ2039 employee人员雇佣 && BZOJ2127 happiness  最小割模型 图论

BZOJ2039 employee人员雇佣 && BZOJ2127 happiness 最小割模型

这俩题是最小割的经典模型,即获得一个点的价值后还可能获得其与其他点的“绑定价值”。对于这样的题,可以先考虑仅有一个“限制关系”,即仅有一个获利规则,然后在此基础上继续添加限制条件。利用最小割,可以将“获得利益”转化为“舍弃最小利益”,然后用总获利减去舍弃的,即为获得的最大利益。在构图时,可以先搞个简···
BZOJ2438 [中山市选2011]杀人游戏 期望概率+tarjan 图论

BZOJ2438 [中山市选2011]杀人游戏 期望概率+tarjan

考试的时候想的是警察一步一步确认凶手,还要缩减比例,所以完全想错了。警察是在同时完成所有调查工作,而且在同一个强连通分量中,警察只要调查一个人,剩下的人就都会被确认,即关系具有传递性。调查每个人,警察都有死亡的概率,所以最终存活的概率即为1-调查的人数/总人数。tarjan缩点建图,入度为0的点数即···
Luogu3128 [USACO15DEC]最大流Max Flow 树上差分 图论

Luogu3128 [USACO15DEC]最大流Max Flow 树上差分

此题不是网络流! 树上差分裸题,将差分思想用在树上。要对整条路径上的点进行操作,可以先考虑对路径的两个端点、LCA以及LCA的父节点进行操作,最后一遍DFS,更新各节点信息。例如在本题中,要将整条路径的点权加1,可以给两个端点分别加1,给LCA减1,再给LCA的父节点减1。完成所有操作后,只需要DF···
BZOJ1098 [POI2007]办公楼biu 链表+BFS 图论

BZOJ1098 [POI2007]办公楼biu 链表+BFS

今天上午考试“最简单”的一道题,一上来很容易就想到了构建反图,然后对每个连通分量计数,搞了半天O(n^2)暴力,还以为能轻松过,后来算了一下内存,才发现162MB的内存,撑死也就算到11000,最后确实也只得了60分。 题解: 考虑优化构建反图,减少无用的枚举次数:将未分配反图中连通分量的点构成链表···
网络流模版 图论

网络流模版

最大流问题:Dinic [crayon-5a5f4e25e3a65072665934/] 最小费用最大流 [crayon-5a5f4e25e3a72610897925/] 还有一个写的好看一些的: [crayon-5a5f4e25e3a76226337742/]