[bzoj 1449] 球队收益(费用流)

Description

Input

Output

一个整数表示联盟里所有球队收益之和的最小值。

Sample Input

3 3

1 0 2 1

1 1 10 1

0 1 3 3

1 2

2 3

3 1

Sample Output

Hint

Solution

这题费用流裸题好吧。

先假设所有队在接下来的比赛中都会输掉，算出收益。

但是一场比赛应该有且只有一支球队赢得比赛，所以真实收益和我们算出来的收益就会有一些差值，再计算最小的差值即可。

我们可以发现，队伍\(i\)每赢得一场比赛，就会多获得\(C_i * (2 * Win_i + 1) - D_i * (2 * Lost_i - 1)\) 的收益，并且由于赢得越多，\(Win_i\)就会越大，\(Lost_i\)就会越小，所以获得的收益差值就会越来越大。于是我们可以建立一个最小费用最大流的模型。

我们建立一个源点，向所有比赛建一条流量为1，费用为0的边。
从比赛向其两支球队建立一条流量为1，费用为0的边。
从每支球队向汇点建x(x是该支球队参加的比赛数)条边，每条边流量为1，费用每赢一场的差值。

PS：这里要注意一点，差值会随着赢的场数增多而增多，所以最小费用最大流一定会先走赢第一场，再走第二场，第三场，等等。。。这是算法正确性的关键。

建好图，然后跑一遍最小费用最大流，加上之前的答案，这题就完了。

Code

#include <cstdio>

#include <queue>

#include <iostream>

using namespace std;

const int maxn = 5e3 + 10, maxm = 1e3 + 10, inf = 1e9 + 7;

int n, m, S, T, cnt;

int w[maxn], l[maxn], a[maxn], b[maxn], x[maxn];

int dis[maxn+maxm], inq[maxn+maxm];

queue<int> q;

struct edge {int u, v, f, c; edge *next, *rev;} e[maxn<<1], *head[maxn+maxm], *from[maxn+maxm];

inline void adde(int u, int v, int flow, int cost) {

	e[cnt] = (edge){u, v, flow, cost, head[u], &e[cnt+1]}, head[u] = &e[cnt++];

	e[cnt] = (edge){v, u, 0, -cost, head[v], &e[cnt-1]}, head[v] = &e[cnt++];

}

bool spfa() {

	while(!q.empty()) q.pop();

	for(int i = 1; i <= m + n + 1; i++) dis[i] = inf, inq[i] = 0, from[i] = NULL;

	dis[S] = 0, inq[S] = 1; q.push(S);

	while(!q.empty()) {

		int u = q.front(); q.pop(), inq[u] = 0;

		for(edge *k = head[u]; k; k = k->next) if(k->f) {

			if(dis[k->v] > dis[u] + k->c) {

				dis[k->v] = dis[u] + k->c;

				from[k->v] = k;

				if(!inq[k->v]) inq[k->v] = 1, q.push(k->v);

			}

		}

	}

	return dis[T] != inf;

}

int mcf() {

	int res = 0, xx = inf;

	for(edge *k = from[T]; k; k = from[k->u]) xx = min(xx, k->f);

	for(edge *k = from[T]; k; k = from[k->u])

		res += xx * k->c, k->f -= xx, k->rev->f += xx;

	return res;

}

int main() {

	int u, v;

	scanf("%d%d", &n, &m);S = 0, T = n + m + 1;

	for(int i = 1; i <= n; i++) scanf("%d%d%d%d", w+i, l+i, a+i, b+i);

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

		scanf("%d%d", &u, &v);

		l[u]++, l[v]++;

		x[u]++, x[v]++;

		adde(S, n+i, 1, 0);

		adde(n + i, u, 1, 0);

		adde(n + i, v, 1, 0);

	}

	int ans = 0;

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

		ans += w[i] * w[i] * a[i] + l[i] * l[i] * b[i];

		for(int j = 0; j < x[i]; j++)

			adde(i, T, 1, a[i]*(2*w[i]+1) - b[i] * (2 * l[i] - 1)),

			w[i]++, l[i]--;

	}

	while(spfa()) ans += mcf();

	printf("%d\n", ans);

	return 0;

}

巴特西

[bzoj 1449] 球队收益(费用流)

[bzoj 1449] 球队收益(费用流)

Description

Input

Output

Sample Input

Sample Output

Hint

Solution

Code

最新文章

热门文章