本文主要是介绍最大流=最小割=最小点权覆盖集=sum-最大点权独立集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
二分图最小点覆盖和最大独立集都可以转化为最大匹配求解。
在这个基础上，把每个点赋予一个非负的权值，这两个问题就转化为：二分图最小点权覆盖和二分图最大点权独立集。
二分图最小点权覆盖
从x或者y集合中选取一些点，使这些点覆盖所有的边，并且选出来的点的权值尽可能小。
建模：
原二分图中的边(u,v)替换为容量为INF的有向边(u,v)，设立源点s和汇点t，将s和x集合中的点相连，容量为该点的权值；
将y中的点同t相连，容量为该点的权值。在新图上求最大流，最大流量即为最小点权覆盖的权值和。
二分图最大点权独立集
在二分图中找到权值和最大的点集，使得它们之间两两没有边。其实它是最小点权覆盖的对偶问题。答案=总权值-最小点覆盖集。
最大流=最小割=最小点权覆盖集=sum-最大点权独立集
题意：一个m*n的棋盘，每个格子都有一个权值，从中取出某些数，使得任意两个数所在的格子没有公共边，并且所取去出的数和最大。求这个最大的值。
解：
将格子染色成二分图，显然是求二分图的最大点权独立集。将问题转化为二分图最小点权覆盖来求解，最终结果=总权和-最大流。
另外： 这个dinic最大流这么写最好写。
const int inf = 0x7fffffff ;
const int maxn = 20000 , maxm = 500000 ;
struct Edge{int v , f ,next ;Edge(){}Edge(int _v , int _f , int _next):v(_v) ,f(_f),next(_next){}
};
int sourse , meet ;
int id ;
Edge e[maxm*2 + 10] ;
int g[maxn + 10] ;void add(int u , int v , int f){e[++id] = Edge(v , f ,g[u]) ;g[u] = id ;e[++id] = Edge(u , 0 , g[v]) ;g[v] = id ;
}queue <int> que ;
bool vis[maxn + 10] ;
int dist[maxn + 10] ;void bfs(){memset(dist , 0 , sizeof(dist)) ;while(! que.empty()) que.pop() ;que.push(sourse) ;vis[sourse] = 1 ;while(! que.empty()){int u = que.front() ; que.pop() ;for(int i = g[u] ; i ; i = e[i].next){int v = e[i].v ;if(e[i].f && !vis[v]){que.push(v) ;dist[v] = dist[u] + 1 ;vis[v] = 1 ;}}}
}int dfs(int u , int delta){if(u == meet) return delta ;int ans = 0 ;for(int i = g[u] ; i && delta ; i = e[i].next){int v = e[i].v ;if(e[i].f && dist[v] == dist[u] + 1){int d = dfs(v , min(delta , e[i].f)) ;e[i].f -= d ;e[i^1].f += d ;delta -= d ;ans += d ;}}return ans ;
}int maxflow(){int ans = 0 ;while(1){memset(vis , 0 , sizeof(vis)) ;bfs() ;if(! vis[meet]) return ans ;ans += dfs(sourse , inf) ;}
}void init(){memset(g , 0 , sizeof(g)) ;id = 1 ;
}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 ;
}
这篇关于最大流=最小割=最小点权覆盖集=sum-最大点权独立集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
