本文主要是介绍poj 2987 Firing，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有n个员工，现在公司要裁员，告诉你裁掉每个员工可以得的到的盈利c，c大于0也可以小于0，现在问你公司的最大盈利为多少，并且在最大盈利的基础上至少炒掉多少人。最大闭合权图：
建立超级源点和使盈利为正数的员工相连，权值为该员工给公司带来盈利，建立超级汇点和使公司盈利为负的员工相连,权值为该员工给公司带来盈利的绝对值，存在从属关系的员工之间连一条边，全值为inf，跑一遍最大流算法即可。#include<stdio.h>
#include<string.h>
#include<iostream>
#define N 200000
#define inf 1000000000
using namespace std;
struct Edge{
long long u,v,c,next;
}edge[1000010];
long long head[80010],pre[80010],cur[1000010],dis[80010],gap[1000010],vis[80010];
long long start,end,n,m,e,a,b,c,sum,num; void add_adge(long long u,long long v,long long c1)
{ edge[e].u=u; edge[e].v=v; edge[e].c=c1; edge[e].next=head[u]; head[u]=e++; edge[e].u=v; edge[e].v=u; edge[e].c=0; edge[e].next=head[v]; head[v]=e++;
}
void dfs(long long u)
{vis[u]=1;for(long long i=head[u]; i!=-1;i=edge[i].next) { if(edge[i].c>0&&!vis[edge[i].v]) {num++;dfs(edge[i].v);}}
}long long sap()
{ long long flow=0,aug=inf,u; long long flag; for(long long i=0; i<=n+1; i++) { cur[i]=head[i]; gap[i]=dis[i]=0; } gap[start]=n+2; u=pre[start]=start; while(dis[start]<n+2) { flag=0; for(long long &j=cur[u]; j!=-1; j=edge[j].next) { long long v=edge[j].v; if(edge[j].c>0&&dis[u]==dis[v]+1) { flag=1; if(edge[j].c<aug) aug=edge[j].c; pre[v]=u; u=v; if(u==n+1) { flow+=aug; while(u!=0) { u=pre[u]; edge[cur[u]].c-=aug; edge[cur[u]^1].c+=aug; } aug=inf; } break; } } if(flag) continue; long long mindis=n+2; for(long long j=head[u]; j!=-1; j=edge[j].next) { long long v=edge[j].v; if(edge[j].c>0&&dis[v]<mindis) { mindis=dis[v]; cur[u]=j; } } if((--gap[dis[u]])==0) break; gap[dis[u]=mindis+1]++; u=pre[u]; } return flow;
}
int main()
{ while(cin>>n>>m){ e=0;start=0;num=0;end=n+1; long long sum=0;memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis));for(long long i=1;i<=n;i++) { cin>>c;if(c>0) {add_adge(0,i,c);sum += c;}else if(c<0) add_adge(i,n+1,-c); } for(long long i=1;i<=m;i++) { cin>>a>>b; add_adge(a,b,inf); } long long ans=sap();sum -= ans;dfs(0);//printf("%lld\n",sum);printf("%lld %I64d\n",num,sum);} return 0;
}
这篇关于poj 2987 Firing的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
