标签为 [图论] 的文章

BZOJ2115 Xor

题目大意 给定一张n个点,m条边的无向图,边上有权。 定义一条路径的权值为这条路径上所有边权的异或和。 求一条1到n的路径,可以经过重复的边和点,使得这条路径的权值最大。输出最大的权值。 Solution 由于权值是异或和,所以把一条路径重复经过两次是没有意义的。贡献答案的,只有图中的一些简单环和一条1到n的路径。 我们可以事先选出一条1到n的路径(任意),记为“主路径”。假设我们沿着这条路径由1走到n,并得到了这条路径的权值,记为ans。 再将所有环的异或和求出来。最后的答案就是在选取一些环的异或和和ans的异或和的最 ......

BZOJ1797 mincut最小割

题目大意 给定一张网络,询问其中的每条有向边是否可能属于某一个最小割,是否一定属于所有最小割。 Solution 题目是最小割,肯定先跑一次网络流模板…… 求出最小割后,就可以得到一个残余网络。如果对这个残余网络进行强联通缩点,可以发现s,t一定不在同一个强联通分量中。否则,s,t之间肯定还能继续增流,求出的肯定不是最大流。 如果原图中一条边是u->v的,且任意一点u缩点后属于belong[u]的强联通分量中。 如果这条边没有满流,显然它不可能属于某一个最小割。 如果belong[u]!=belong[v],则边u->v可以属于某一个最小割。 ......