最大流
本文共 428 字，大约阅读时间需要 1 分钟。
对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。
设棋盘是黑白相间的，
每个黑点只跟周围相邻的白点联通，白点也只跟周围相邻的黑点联通，有一个共同的源S
连到黑点，每条边的容量就是黑点上面的数字，黑点同白点之间的连线，容量都看作无穷大， 所有白点都连到一个共同的汇点T，权值就是白点上面的数字，如果从源S 到T 之间的最大 流=所有黑点上面的数字和同时=所有白点上面的数字和，那么该矩阵就是可以被还原的， 以上是最大流的解法，肯定可以得出正确的结果，但至于是否为最优方法，就不一定了。如果黑点加1，肯定有一个白点要加1；如果白点加1,则肯定有一个黑点加1。所以最好所有黑点之和与所有白点之和是相等的。
则定义最大流的方向，只允许从黑点向白点的方向，最后，在白点的汇点汇合。
从s到黑点，以及从白点到T的边的容量都满了，说明必须是最大流才能实现
转载地址：http://vpeti.baihongyu.com/
你可能感兴趣的文章
日志框架学习2
查看>>
SVN-无法查看log，提示Want to go offline，时间显示1970问题,error主要是 url中 有一层的中文进行了2次encode
查看>>
NGINX
查看>>
Qt文件夹选择对话框
查看>>
DeepLearning tutorial（7）深度学习框架Keras的使用-进阶
查看>>
第三方SDK：JPush SDK Eclipse
查看>>
第三方开源库：imageLoader的使用
查看>>
Android studio_迁移Eclipse项目到Android studio
查看>>
JavaScript setTimeout() clearTimeout() 方法
查看>>
CSS border 属性及用border画各种图形
查看>>
转载知乎-前端汇总资源
查看>>
JavaScript substr() 方法
查看>>
JavaScript slice() 方法
查看>>
JavaScript substring() 方法
查看>>
HTML 5 新的表单元素 datalist keygen output
查看>>
（转载）正确理解cookie和session机制原理
查看>>
jQuery ajax - ajax() 方法
查看>>
将有序数组转换为平衡二叉搜索树
查看>>
最长递增子序列
查看>>
从一列数中筛除尽可能少的数，使得从左往右看这些数是从小到大再从大到小...
查看>>