BZOJ 1497 [NOI2006]最大获利

Description

新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后，公司得到了一共N个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第i个通讯中转站需要的成本为Pi（1≤i≤N）。另外公司调查得出了所有期望中的用户群，一共M个。关于第i个用户群的信息概括为Ai, Bi和Ci：这些用户会使用中转站Ai和中转站Bi进行通讯，公司可以获益Ci。（1≤i≤M, 1≤Ai, Bi≤N） THU集团的CS&T公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和）

Input

输入文件中第一行有两个正整数N和M 。第二行中有N个整数描述每一个通讯中转站的建立成本，依次为P1, P2, …, PN 。以下M行，第(i + 2)行的三个数Ai, Bi和Ci描述第i个用户群的信息。所有变量的含义可以参见题目描述。

Output

你的程序只要向输出文件输出一个整数，表示公司可以得到的最大净获利。

Sample Input

5 5

1 2 3 4 5

1 2 3

2 3 4

1 3 3

1 4 2

4 5 3

Sample Output

HINT

【样例说明】选择建立1、2、3号中转站，则需要投入成本6，获利为10，因此得到最大收益4。

【评分方法】本题没有部分分，你的程序的输出只有和我们的答案完全一致才能获得满分，否则不得分。

【数据规模和约定】 80%的数据中：N≤200，M≤1 000。 100%的数据中：N≤5 000，M≤50 000，0≤Ci≤100，0≤Pi≤100。

Solution

题解是参考的胡伯涛写的《最小割模型在信息学竞赛中的应用》以及http://blog.csdn.net/eod_realize/article/details/41479891。

容易看到这是一个最大权闭合子图，建图方法为S与正权值点连边，有负权值的点与T连边，边权都是点权绝对值，原图中的连边不变，边权为正无穷。

有一个很重要的性质，我们建出来的图的每一个割都代表一种选择方案，即放弃某些基站和收益。

于是，答案为所有的收益减去这个图中最小割。

求最小割可以用最大流算法。

最大流算法用Dinic解决就好了。

写这道题的时候我连Dinic都不知道是什么鬼，一头雾水地写了一遍，各种WA啊 …

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <cstdio>
#include <queue>
const int INF = 1000000007;
const int maxn = 5010;
const int maxm = 50010;
const int maxnode = maxn + maxm + 100;
int n, m, tot, t, s;
int getint() {
    int r = 0; char c = getchar();
    for (; c < '0' || c > '9'; c = getchar());
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r;
}
int min(int a, int b) {
    return a < b ? a : b;
}
struct edge_type {
    int to, next, r;
} edge[(maxm * 3 + maxn) << 1];
int cnte = 0, h[maxnode];
void ins(int u, int v, int w) {
    edge[cnte].to = v;
    edge[cnte].next = h[u];
    edge[cnte].r = w;
    h[u] = cnte++;
    edge[cnte].to = u;
    edge[cnte].next = h[v];
    edge[cnte].r = 0;
    h[v] = cnte++;
}
int q[maxnode];
int dep[maxnode], cur[maxnode], head, tail;
bool bfs() {
	head = tail = 0;
	q[tail++] = s;
	for (int i = 1; i <= t; ++i) { dep[i] = -1; }
	dep[s] = 0;
	int now, v;
	while (head < tail) {
		now = q[head++];
		for (int i = h[now]; i != -1; i = edge[i].next) {
			v = edge[i].to;
			if (dep[v]!=-1) continue;
			if (edge[i].r) {
				dep[v] = dep[now] + 1;
				q[tail++] = v;
				if (v == t) return true;
			}
		}
	}
	return false;
}
int dfs(int now, int a) {
	if (now == t || a == 0) return a;
	int ret = 0, f;
	for (int &i = cur[now]; i != -1; i = edge[i].next) {
		if (dep[edge[i].to] != dep[now] + 1) continue;
		if (f = dfs(edge[i].to, min(a, edge[i].r))) {
			edge[i].r -= f;
			edge[i^1].r += f;
			ret += f;
			a -= f;
			if (!a) break;
		}
	}
	if (!ret) dep[now] = -1;
	return ret;
}
int ans = 0;
void MaxFlow() {
	int tmp;
	while (bfs()) {
		for (int i = 0; i <= t; ++i) cur[i] = h[i];
		while (tmp = dfs(s, INF)) ans -= tmp;
	}
}
int main () {
    n = getint(); m = getint();
    tot = n + m; t = tot + 1; s = 0;
    for (int i = 0; i <= t; ++i) h[i] = -1;
    int x, y, z;
    for (int i = m + 1; i <= tot; ++i) {
        x = getint();
        ins(i, t, x);
    }
    for (int i = 1; i <= m; ++i) {
        x = getint(); y = getint(); z = getint();
        ans += z;
        ins(s, i, z);
        ins(i, x + m, INF);
        ins(i, y + m, INF);
    }
    MaxFlow();
    printf("%d", ans);
}