放牧代码和思想
专注自然语言处理、机器学习算法
    愛しさ 優しさ すべて投げ出してもいい

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//////////////////////////////////

13769705 hankcs 2987 Accepted 2444K 1047MS C++ 2660B 2015-01-08 22:50:43

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

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的作品

HanLP自然语言处理包《自然语言处理入门》