POJ 2987 Firing【最大权闭合图-最小割】

时间:2021-06-04 01:56:47

题意:给出一个有向图,选择一个点,则要选择它的可以到达的所有节点。选择每个点有各自的利益或损失。求最大化的利益,以及此时选择人数的最小值。

算法:构造源点s汇点t,从s到每个正数点建边,容量为利益。每个负点到t建边,容量为损失的绝对值。其他关系边容量正向无穷,反向0。正数点总和减去最小割即为最大权闭合图答案。因为残余网络不会对0流边处理,所以不会将0流点选入取点集,所以最小割的取法中为被选中的点。

最大权闭合图的求解方法:

  1. 先构造网络流N,添加源点s,从s到正权值点做一条边,容量为点的权值。

  2. 添加汇点t,从负权值点到t做一条边,容量为点的权值的绝对值。

  3. 原来的边的容量统统设为无穷大。比如:

    POJ 2987 Firing【最大权闭合图-最小割】转换为

    POJ 2987 Firing【最大权闭合图-最小割】

  4. 求解最小割:最大权=正权值之和-最小割权值

  5. 残余网络中的点的个数即为裁员个数。

思路:最大权闭合图。用Dinic求最小割

要得到最大收益,就是尽量选择更多收益为正数的人,选择更少收益为负数的人,因此我们将收益为正数的人与源点连一条边,将收益为负数的人与汇点连一条边,这样得到的割集就是未选择的收益为正数的人+选择的收益为负数的人(也可以是损失的收益),要使这个割集越小越好,那么就是求最小割。最大收益是所有正数的和sum,再用sum-最小割(损失的收益)就可以得到最大收益。

最少的裁员人数,最小割后的的残余网络中,只要能从S遍历到的点,就可以看成是被裁掉的点,因为最终肯定会遇到割边达不到T,所以我们直接DFS残余网络的点数就可以得到最少的裁员人数了。

 #include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long LL; const LL INF = 0x3f3f3f3f3f3f3f3f; struct edge
{
edge(int _v,int _r, LL _c):v(_v),r(_r),c(_c){};
int v,r;
LL c;
}; vector<edge> e[]; void add_edge(int u,int v,LL c)
{
e[u].push_back(edge(v,e[v].size(),c));
e[v].push_back(edge(u,e[u].size()-,));
} int level[];
int iter[]; // 当前弧,在其之前的边已经没有用了
queue<int> q; bool bfs(int s,int t)
{
memset(level,, sizeof(level));
while (!q.empty()) q.pop();
q.push(s);
level[s]=;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=;i<e[u].size();i++)
{
int v=e[u][i].v;
if(e[u][i].c>&&!level[v])
{
q.push(v);
level[v]=level[u]+;
}
if(level[t])return ;
}
}
return ;
} LL dfs(int s,int t, LL flow)
{
if(s==t)return flow;
for(int& i = iter[s];i<e[s].size();i++) // 一次增广返回时,记录当前弧
{
int v = e[s][i].v;
if(e[s][i].c>&&level[v]==level[s]+)
{
LL k = dfs(v,t,min(flow,e[s][i].c));
if(k>)
{
e[s][i].c-=k;
e[v][e[s][i].r].c+=k;
return k;
}
}
}
return ;
} LL Dinic(int s,int t)
{
LL flow=;
while(bfs(s,t))
{
LL f=;
memset(iter, , sizeof(iter));
while((f=dfs(s,t,INF))>)flow+=f;
}
return flow;
} bool vis[];
int cnt;
void GaoCnt(int u)//dfs统计残余图的正边
{
++cnt;
vis[u]=;
for(int i=;i<e[u].size();i++)
{
int v=e[u][i].v;
if(e[u][i].c>&&!vis[v])
GaoCnt(v);
}
} int main()
{
int n,m;
scanf("%d%d",&n,&m);
int s=,t=n+;// 源点,汇点
LL ans=;
for(int i=;i<=n;i++)
{
LL c;
scanf("%lld",&c);
if(c>)
{
ans+=c; //正权值求和
add_edge(s,i,c);
}
else if(c<)
{
add_edge(i,t,-c);
}
}
for (int i = ; i < m; ++i) {
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v,INF);
}
ans-= Dinic(s,t);
GaoCnt(s);
printf("%d %lld\n",cnt-,ans);
return ;
}

参考自:hankcsyogykwan