本文主要是介绍poj2987--Firing（最大权闭合图），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
poj2987：题目链接
题目大意：有个公司，n个员工，m个关系，因为亏损，所以要辞退一些员工，给出辞退每个员工会给带来的收益（有正有负），关系x y代表x是y的上司，如果辞退一个上司，那么他手下的人都会退出，问最大的收益，和要删除的人数。
因为删掉一个上司，员工也会离开，所以最后求的删除的人会是一个闭合图，也就是求最大权闭合图，将其中正值k的点i连接边<s,i>值为正，原图中的边值为正无穷，负值k的点j连接边<j,t>值为-k，这样求得最小割，也就是一个简单割，其中s集合所在的点就是最大权闭合图中的点。计算收益的时候用正值的和-最小割
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std ;
#define LL __int64
struct node{LL u , v , w ;int next ;
}edge[200000];
int head[6000] , cnt , l[6000] ;
int vis[6000] , num ;
queue <int> que ;
void add(LL u,LL v,LL w) {edge[cnt].u = u ; edge[cnt].v = v ; edge[cnt].w = w ;edge[cnt].next = head[u] ; head[u] = cnt++ ;edge[cnt].u = v ; edge[cnt].v = u ; edge[cnt].w = 0 ;edge[cnt].next = head[v] ; head[v] = cnt++ ;
}
int bfs(int s,int t) {memset(l,-1,sizeof(l)) ;while( !que.empty() ) que.pop() ;l[s] = 0 ; que.push(s) ;int i , u , v ;while( !que.empty() ) {u = que.front() ;que.pop() ;for(i = head[u] ; i != -1 ; i = edge[i].next) {v = edge[i].v ;if( l[v] == -1 && edge[i].w > 0 ) {l[v] = l[u] + 1 ;que.push(v) ;}}}if( l[t] > 0 ) return 1 ;return 0 ;
}
LL dfs(int u,int t,LL min1) {if( u == t ) return min1 ;int i , v ;LL temp , ans = 0 ;for(i = head[u] ; i != -1 ; i = edge[i].next) {v = edge[i].v ;if( l[v] == l[u]+1 && edge[i].w && ( temp = dfs(v,t,min(min1,edge[i].w) ) ) ) {edge[i].w -= temp ; edge[i^1].w += temp ;min1 -= temp ; ans += temp ;}if( !min1 ) break ;}if( ans ) return ans ;l[u] = -1 ;return 0 ;
}
void f_dfs(int u) {int i , v ;for(i = head[u] ; i != -1 ; i = edge[i].next) {v = edge[i].v ;if( vis[v] || edge[i].w == 0 ) continue ;vis[v] = 1 ;num++ ;f_dfs(v) ;}
}
int main() {int n , m ;int i , j , u , v , x ;LL inf = (LL)1e16 , max_flow , temp , sum ;while( scanf("%d %d", &n, &m) != EOF ) {memset(head,-1,sizeof(head)) ;cnt = sum = 0 ;for(i = 1 ; i <= n ; i++) {scanf("%d", &x) ;if( x > 0 ) sum += x , add(0,i,x) ;else add(i,n+1,-x) ;}while( m-- ) {scanf("%d %d", &u, &v) ;add(u,v,inf) ;}max_flow = 0 ;while( bfs(0,n+1) ) {while( temp = dfs(0,n+1,inf) )max_flow += temp ;}memset(vis,0,sizeof(vis)) ;vis[0] = 1 ;num = 0 ;f_dfs(0) ;printf("%d %lld\n", num , sum-max_flow) ;}return 0 ;
}
这篇关于poj2987--Firing（最大权闭合图）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
