本文主要是介绍hdu 1569 and hdu 3657 最小割，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
hdu1569
给你一个m*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取数所在的2个格子不能相邻，并且取出的数的和最大。
按国际象棋黑白染色,源点到黑点容量为数字,黑点到它周围的白点容量为无穷,白点到汇点容量为数字,最后答案为总值减去最小割（摘自网上）。
（行+列）= 奇数 黑子 连T
（行+列）= 偶数 白子 连S
没有黑白相邻 ， 意味着 ，S 到T没有路可走。 否则 S->黑->白->T 。
<=> 最小的花费把S-T之间的路切开。
U - V 分开最小的权和， 也就是求最小割。
为啥将黑->白权值设为inf ？
这条边“死都存在”，不能人为的移走，那么就是“死都存在”。
意味着不能切割黑->白之间的边。
int main(){int n , m , i , j , u , v , c , sum ;while(scanf("%d%d" ,&n ,&m) != EOF){init() ;sum = 0 ;sourse = 0 ;meet = n*m + 1 ;for(i = 1 ; i <= n ; i++){for(j = 1 ; j <= m ; j++){scanf("%d" ,&c) ;sum += c ;u = (i-1) * m + j ;if((i+j)&1)add(u , meet , c) ;else{add(sourse , u , c) ;if(i > 1)add(u , u-m , inf) ;if(i < n)add(u , u+m , inf) ;if(j > 1)add(u , u-1 , inf) ;if(j < m)add(u , u+1 , inf) ;}}}printf("%d\n" , sum - maxflow()) ;}return 0 ;
}hdu 3657
题目描述：n*m的矩阵，每个位置都有一个正数，一开始你的分数是0，当你取走一个数字时，你的分数增加那个分数。如果你取完数字后，新出现了2个相邻的都是空的格子，那么你的分数减少2 * ( x & y)，x，y是那两个格子的原始数值。
同时有一些附加条件，有一些格子的数字是必须拿走的。
-----------------------
同上题
----------------------
为啥将黑->白权值设为2*(x&y) ？
因为切割黑-白之间的路可以“人为的移走”，不是“死都存在”的边。
对于必须选择的棋子，将权值设为inf。也就是说最小割集不会选择此边<=>此点必选。
int w[58][58] ;
bool is[58][58] ;int main(){int n , m , i , j , k , u , sum ;while(cin>>n>>m>>k){sum = 0 ;init() ;sourse = 0 , meet = n*m + 1 ;for(i = 1 ; i <= n ; i++){for(j = 1 ; j <= m ; j++){scanf("%d" ,&w[i][j]) ;sum += w[i][j] ;}}memset(is , 0 , sizeof(is)) ;while(k--){scanf("%d%d" ,&i ,&j) ;is[i][j] = 1 ;}for(i = 1 ; i <= n ; i++){for(j = 1 ; j <= m ; j++){u = (i-1)*m + j ;if((i+j)&1){if(is[i][j])add(u , meet , inf) ;elseadd(u , meet , w[i][j]) ;}else{if(is[i][j])add(sourse , u , inf) ;elseadd(sourse , u , w[i][j]) ;if(i > 1)add(u , u-m , 2*(w[i][j]&w[i-1][j])) ;if(i < n)add(u , u+m , 2*(w[i][j]&w[i+1][j])) ;if(j > 1)add(u , u-1 , 2*(w[i][j]&w[i][j-1])) ;if(j < m)add(u , u+1 , 2*(w[i][j]&w[i][j+1])) ;}}}printf("%d\n" , sum - maxflow()) ;}return 0 ;
}
这篇关于hdu 1569 and hdu 3657 最小割的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
