「NOI2006」最大获利

传送门

最小割。

对于每一组用户群 $A_i, B_i, C_i$ ，连边 $S \to A_i, S \to B_i, $ 容量为成本，还有 $i \to T$ ，容量为收益 $C_i$，$A_i, B_i$ 都向 $i$ 连边，容量为 $inf$ ，割掉与 $S$ 的连边表示支付成本，割掉与 $T$ 的连边表示放弃收益。

参考代码：

#include <algorithm>

#include <cstring>

#include <cstdio>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

template < class T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while ('0' > c || c > '9') f |= c == '-', c = getchar();

	while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

const int _ = 55010, __ = 155010, INF = 2147483647;

int tot = 1, head[_];

struct Edge { int ver, cap, nxt; } edge[__ << 1];

inline void Add_edge(int u, int v, int d) { edge[++tot] = (Edge) { v, d, head[u] }, head[u] = tot ; }

inline void link(int u, int v, int d) { Add_edge(u, v, d), Add_edge(v, u, 0); }

int n, m, s, t, dep[_], cur[_], Q[_];

inline int bfs() {

	int hd = 0, tl = 0;

	memset(dep, 0, sizeof (int) * (t - s + 1));

	Q[++tl] = s, dep[s] = 1;

	while (hd < tl) {

		int u = Q[++hd];

		for (rg int i = head[u]; i; i = edge[i].nxt) {

			int v = edge[i].ver;

			if (dep[v] == 0 && edge[i].cap > 0)

				dep[v] = dep[u] + 1, Q[++tl] = v;

		}

	}

	return dep[t] > 0;

}

inline int dfs(int u, int flow) {

	if (u == t) return flow;

	for (rg int& i = cur[u]; i; i = edge[i].nxt) {

		int v = edge[i].ver;

		if (dep[v] == dep[u] + 1 && edge[i].cap > 0) {

			int res = dfs(v, min(flow, edge[i].cap));

			if (res) { edge[i].cap -= res, edge[i ^ 1].cap += res; return res; }

		}

	}

	return 0;

}

inline int Dinic() {

	int res = 0;

	while (bfs()) {

		for (rg int i = s; i <= t; ++i) cur[i] = head[i];

		while (int d = dfs(s, INF)) res += d;

	}

	return res;

}

int main() {

#ifndef ONLINE_JUDGE

	file("cpp");

#endif

	int sum = 0;

	read(n), read(m), s = 0, t = n + m + 1;

	for (rg int x, i = 1; i <= n; ++i) read(x), link(s, i, x);

	for (rg int x, y, z, i = 1; i <= m; ++i)

		read(x), read(y), read(z), link(x, i + n, INF), link(y, i + n, INF), link(i + n, t, z), sum += z;

	printf("%d\n", sum - Dinic());

	return 0;

}

巴特西

「NOI2006」最大获利

「NOI2006」最大获利

最新文章

热门文章