BZOJ 网络流题目总结

发布于 2017-06-07  461 次阅读


做了一点点题,现在放出来 qwq 方便大爷来 D 和自己复习...

链接直接挂到了自己的题解上 orz 防止误入说一下 建模题解部分文字为白色 

约定


在下面的建模中,我们记 S 点为源点,T 点为汇点

a 点连来 b 点一条 c 为连接有向边 a->b 边权为 c  

b 点连去 a 点一条 c 为连接有向边 b->a 边权为 c

最大流 


BZOJ 1711 [Usaco2007 Open]Dining 吃饭

题意:n 头牛,f 种食物,d 种饮料,一头牛一种食物一种饮料,求最大匹配...

建模: 拆牛点为牛出点 牛入点 以限制每头牛只能跑一次 牛入点向牛出点连 1 S 点连向每个 f 点一条 1 f 点向对应的牛入点连一条 1 牛出点向对应的 d 点连一条 1 每个 d 点向 T 点连一条 1 最大流

 

 

最小割


BZOJ 1412 狼和羊的故事

题意:一个 n*m 的网格图,边框均为篱笆,有一些点是狼,一些点是羊,在边上建篱笆,使得狼吃不到羊,一单位长度的篱笆费用为 1

建模: 对于狼 S 点连来一条 inf 对于羊 连去 T 点一条 inf 对于格子 向四周连去 1 此时若 T 点有流量 则狼能吃到羊 最小割即可

BZOJ 3996 [TJOI2015] 线性代数

题意:给出一个 n*n 的矩阵 A,1*n 的矩阵 C,求出一个 1*n 的 01 矩阵 A,使得\(D=(A*B-C)*A^T\) 最大,输出 D...

建模: 转化问题为:对于 n 个物品,选择 i 物品的代价是\(c_i\),同时选择 i,j 的收益是\(b_{ij}\) 一个经典最大全闭合子图的模型 连边方式为:对于收益点,S 点连向点 ij 一条\(b_{ij}\),点 ij 分别连向 i,j 一条 inf,对于代价点 i,连向 T 点一条\(c_i\) 最小割即可

BZOJ 1475 方格取数

题意:对于一个 n*n 的网格图,选择了一个点就不能选择与它相邻的点,求最大选择权值和...

建模: 黑白染色,奇点和偶点间互斥,显然二分图模型,二分图最大点权独立集=sum-二分图最小点权覆盖。二分图最小点权覆盖建模方案为原图边(此题为互斥点对)权改为 inf,确保不会被割,S 点 T 点分别连向一边,权值为点权,最小割即可。

BZOJ 1324 Exca 王者之剑

题意:网格图,点有点权,走两步拿一个点... 求最大收益

建模: 同上一题...

 


一个非常弱的准退役OIER