POJ 2987 Firing 题解 《挑战程序设计竞赛》

POJ 2987 Firing

大裁员：公司官僚成风，盘根错节，办实事的码农没几个。老板决定大裁员，每开除一个人，同时要将其下属一并开除，如果该下属还有下属，照斩不误。给出每个人的贡献值和从属关系，求最小裁员数及最大贡献值和。

3.5借助水流解决问题的网络流

最大流

妈蛋，再复习下去人要变蠢了！刷一题维护一下智商。

其实题目要求的是最大权闭合图，所谓闭合图，指的是图中每个点的后续都在图中。最大权闭合图，指的是点的权值之和最大的闭合图。

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

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

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

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

   转换为

   

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

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

至于证明，请参考《算法合集之《最小割模型在信息学竞赛中的应用》.pdf》，我看完后觉得除了费口舌讲解之外，还算很好理解的。

至于最小割的求解，可以使用dinic算法。

唯一值得提醒的是，int会溢出，要用long long，不然会WA。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef long long LL;
#define MAX_V 5000 + 16

// 用于表示边的结构体（终点、容量、反向边）
struct edge
{
	int to, rev;
	LL cap;
	edge(int to, LL cap, int rev) :to(to), cap(cap), rev(rev){}
};

vector<edge> G[MAX_V];	// 图的邻接表表示
int level[MAX_V];		// 顶点到源点的距离标号
int iter[MAX_V];		// 当前弧，在其之前的边已经没有用了

// 向图中加入一条从from到to的容量为cap的边
void add_edge(int from, int to, int cap)
{
	G[from].push_back(edge(to, cap, G[to].size() ));
	G[to].push_back(edge(from, 0, G[from].size() - 1));
}

// 通过BFS计算从源点出发的距离标号
void bfs(int s)
{
	memset(level, -1, sizeof(level));
	queue<int> que;
	level[s] = 0;
	que.push(s);
	while (!que.empty())
	{
		int v = que.front(); que.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;
				que.push(e.to);
			}
		}
	}
}

// 通过DFS寻找增广路
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[v] < level[e.to])
		{
			LL 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;
}

// 求解从s到t的最大流
LL max_flow(int s, int t)
{
	LL flow = 0;
	for (;;)
	{
		bfs(s);
		if (level[t] < 0) 
		{
			return flow;
		}
		memset(iter, 0, sizeof(iter));
		LL f;
		while ((f = dfs(s, t, 0x3f3f3f3f3f3f3f3f)) > 0)
		{
			flow += f;
		}
	}
}

int vertex_count, visited[MAX_V];
// 遍历残余网络
void solve(int v)
{
	++vertex_count;
	visited[v] = true;
	for (int i = 0; i < int(G[v].size()); ++i) 
	{
		const edge &e = G[v][i];
		if (e.cap > 0 && !visited[e.to]) 
		{
			solve(e.to);
		}
	}
}
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n, m, w;
	LL W = 0;
	scanf("%d%d", &n, &m);
	const int s = 0, t = n + 1;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &w);
		if (w > 0)
		{
			W += w;
			add_edge(s, i, w);
		}
		if (w < 0)
		{
			add_edge(i, t, -w);
		}
	}

	int u, v;
	for (int i = 0; i < m; ++i)
	{
		scanf("%d%d", &u, &v);
		add_edge(u, v, 0x3f3f3f3f3f3f3f3f);
	}

	LL max_profit = W - max_flow(s, t);
	solve(s);
	printf("%d %I64d\n", --vertex_count, max_profit);
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2987 Firing 题解 《挑战程序设计竞赛》