POJ2987_Firing_最大权闭合图

大致题意

公司要裁员，裁掉每个人都有一个收益，这个收益可正可负。如果要裁掉一个人，他的下属也要全部裁掉，同理，下属的下属也要被裁掉。求最优方案，使最终收益最大化。输出裁掉的人数和最大化的收益。

思路

根据题意可以抽象为：图上的每一个点都有一个权值，并且这个权值可能是负的，求最大权值闭合图。

求解最大权闭合图需要用最小割，具体做法如下：

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

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

原来的边的容量统统设为无穷大。

求解最小割，最大权=正权值之和-最小割权值

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

推导与证明见  最小割在信息学竞赛中的应用

题目链接

http://poj.org/problem?id=2987

AC代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;

typedef long long LL;
struct edge
{
	int to, rev;
	LL cap;
	edge(int a, LL b, int c)
	:to(a), cap(b), rev(c){}
};

const int maxn = 5000 + 100;
const LL inf  = 0x3f3f3f3f3f3f3f3f;

int n, m;
vector<edge> G[maxn];
int level[maxn];
int iter [maxn];
bool vis [maxn];//最后用来构造最大权闭合图

void Add(int from, int to, LL cap)
{
	G[from].push_back(edge(to, cap, G[to].size()));
	G[to].push_back(edge(from, 0, G[from].size()-1));
}

void bfs(int s)
{
	memset(level, -1, sizeof(level));
	level[s] = 0;
	queue<int> qu;
	qu.push(s);

	while(qu.size())
	{
		int v = qu.front();qu.pop();

		for(int i= 0; i< G[v].size(); i++)
		{
			edge e = G[v][i];

			if(e.cap > 0 && level[e.to] < 0)
			{
				level[e.to] = level[v] + 1;
				qu.push(e.to);
			}
		}
	}
}

LL dfs(int v, int t, LL f)
{
	if(v == t) return f;

	for(int &i= iter[v]; i< G[v].size(); i++)
	{
		edge &e = G[v][i];

		if(e.cap > 0 && level[e.to] > level[v])
		{
			int d = dfs(e.to, t, min(f, e.cap));
			if(d > 0)
			{
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}

	return 0;
}

LL max_flow(int s, int t)
{
	LL flow = 0;

	while(1)
	{
		bfs(s);
		if(level[t] < 0) return flow;

		memset(iter, 0, sizeof(iter));

		while(1)
		{
			int f = dfs(s, t, inf);
			if(f > 0) flow += f;
			else break;
		}
	}

}

//从源点出发深搜构造最大权闭合图
int sum(int v)
{
	int res = 1;
	vis[v] = true;

	for(int i= 0; i< G[v].size(); i++)
	{
		edge e = G[v][i];

		if(e.cap > 0 && !vis[e.to])
			res += sum(e.to);
	}

	return res;
}

int main()
{
	//点数、边数
	scanf("%d %d", &n, &m);

	LL W = 0;

	//输入权值
	for(int i= 1; i<= n; i++)
	{
		LL w;
		scanf("%lld", &w);

		if(w > 0)
		{
			//源点向正权值点的边
			Add(0, i, w);
			//正权值点的权值之和
			W += w;
		}

		//负权值点向汇点的边
		else if(w < 0) Add(i, n+1, -w);
	}

	for(int i= 0; i< m; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);

		//原图中的边置为inf
		Add(x, y, inf);
	}

	//求最大权值
	LL res = W - max_flow(0, n+1);
	//求最大权闭合图中的点数
	int cnt = sum(0) - 1;

	cout << cnt << " " << res << endl;

	return 0;
}