@hdu - 6598@ Harmonious Army

@description@
@solution@
@accepted code@
@details@

@description@

n 个士兵，每个士兵可以选择加入 A 组或 B 组。

有 m 个组合技可以增加整个军队的力量：第 i 个组合技涉及到士兵 ui 与 vi，当两人同时加入 A 组力量值增加 ai，同时加入 B 组力量值增加 ci，否则力量值增加 bi。

求每种安排士兵的方案中军队的力量值最大可以为多少。

Input

多组数据。

每组数据开头包含两个正整数 n(n≤500) 和 m(m≤10^4)。

接下来 m 行，每行包含 5 个整数 u,v,a,b,c(1≤u,v≤n,u≠v,1≤a,b,c≤4×10^6)，含义如上。保证同一对 (u, v) 只会出现一次。

保证 n 总和不超过 5×10^3，m 总和不超过 5×10^4。

Output

对于每组数据，输出最大力量值。

Sample Input

3 2

1 2 8 3 3

2 3 4 3 6

Sample Output

12

@solution@

这道题这么多年过去。。。怕不是已经成了套路题。。。

【注：因为我懒所以本来下面应该有讲解的图，但是被我咕了】

我们考虑使用最小割，用所有收益的总和 - 最小割代表的最小代价。

考虑建图：s 向 x 连边，x 向 t 连边。如果割前一条表示选择 A 组，割后一条表示选择 B 组。

考虑 m 对关系，我们先设 (s, u) 容量为 e，(s, v) 容量为 f；(u, t) 容量为 g，(v, t) 容量为 h；(u, v) 容量为 p，(v, u) 容量为 q。

则接下来我们分类讨论 u, v 的选择情况，求出其应该舍弃的收益（即代价）与应该割的边的对应关系。

u 选 A 组，v 选 A 组：对应割 (s, u), (s, v)；其代价为 b + c；其对应的边容量和为 e + f。

u 选 B 组，v 选 B 组：对应割 (u, t), (v, t)；其代价为 a + b；其对应的边容量和为 g + h。

u 选 A 组，v 选 B 组：对应割 (s, u), (v, t), (v, u)；其代价为 a + c；其对应的边容量和为 e + h + q。

u 选 B 组，v 选 A 组：对应割 (u, t), (s, v), (u, v)；其代价为 a + c；其对应的边容量和为 g + f + p。

由上，可以得到 e + f = b + c 等方程。注意到只有 a, b, c 为常量，所以这个方程可能有很多解。

在此处，我们仅考虑一组特殊解，即令 p = q, e = f, g = h。此时可以解出 e = f = (b + c) / 2, g = h = (a + b) / 2, p = q = (a + c) / 2 - b。

于是，我们可以对于每个 x 统计与 x 有关的组合技中 (b + c) / 2 之和与 (a + b) / 2 之和（分别记为 s1[x], s2[x]），然后 s 向 x 连容量为 s1[x] 的边，x 向 t 连容量为 s2[x] 的边。

两个点之间如果有组合技，则连一条双向的、容量为 (a + c) / 2 - b 的边。

这样跑最小割就可以跑出最小代价。除以 2 什么的可以把所有容量乘 2 再最后除回来。

@accepted code@

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

const ll INF = (1LL<<60);

const int MAXN = 500;

const int MAXM = 10000;

const int MAXV = MAXN;

const int MAXE = 4*(MAXN + MAXM);

struct FlowGraph{

	struct edge{

		int to; ll cap, flow;

		edge *nxt, *rev;

	}edges[MAXE + 5], *adj[MAXV + 5], *ecnt;

	int d[MAXV + 5], vd[MAXV + 5], s, t;

	void init(int n) {

		for(int i=1;i<=n;i++)

			d[i] = vd[i] = 0, adj[i] = NULL;

		ecnt = &edges[0];

	}

	void addedge(int u, int v, ll c) {

		edge *p = (++ecnt), *q = (++ecnt);

		p->to = v, p->cap = c, p->flow = 0;

		p->nxt = adj[u], adj[u] = p;

		q->to = u, q->cap = 0, q->flow = 0;

		q->nxt = adj[v], adj[v] = q;

		p->rev = q, q->rev = p;

	}

	ll aug(int x, ll tot) {

		if( x == t ) return tot;

		int mind = t + 1; ll sum = 0;

		for(edge *p=adj[x];p;p=p->nxt) {

			if( p->cap > p->flow ) {

				if( d[p->to] + 1 == d[x] ) {

					ll del = aug(p->to, min(tot - sum, p->cap - p->flow));

					sum += del, p->flow += del, p->rev->flow -= del;

					if( sum == tot || d[s] == t + 1 ) return sum;

				}

				mind = min(mind, d[p->to]);

			}

		}

		if( sum == 0 ) {

			vd[d[x]]--;

			if( vd[d[x]] == 0 ) {

				d[s] = t + 1;

				return sum;

			}

			d[x] = mind + 1;

			vd[d[x]]++;

		}

		return sum;

	}

	ll max_flow(int _s, int _t) {

		s = _s, t = _t;

		ll flow = 0;

		while( d[s] != t + 1 )

			flow += aug(s, INF);

		return flow;

	}

}G;

ll x[MAXN + 5], y[MAXN + 5];

int main() {

	int n, m;

	while( scanf("%d%d", &n, &m) == 2 ) {

		G.init(n + 2);

		for(int i=1;i<=n;i++)

			x[i] = y[i] = 0;

		ll ans = 0;

		int s = n + 1, t = n + 2;

		for(int i=1;i<=m;i++) {

			int u, v, a, b, c;

			scanf("%d%d%d%d%d", &u, &v, &a, &b, &c);

			x[u] += a + b, x[v] += a + b;

			y[u] += c + b, y[v] += c + b;

			G.addedge(u, v, a + c - 2*b);

			G.addedge(v, u, a + c - 2*b);

			ans += a + b + c;

		}

		for(int i=1;i<=n;i++)

			G.addedge(s, i, x[i]), G.addedge(i, t, y[i]);

		printf("%lld\n", ans - G.max_flow(s, t)/2);

	}

}

@details@

不要问我为什么即使用了 long long 还是跑得非常快，问就是 O(能过)。

原题目还给了 a, b, c 之间种种不可描述的关系。。。但其实也是用来迷惑人的。。。

巴特西

@hdu - 6598@ Harmonious Army

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章