现在 etc bfs ostream 两个 cstring main bzoj
其中 x,y 分别表示这只球队本赛季的胜负场次。现在赛季进行到了一半,每只球队分别取得了 a[i] 场胜利和 b[i] 场失利。而接下来还有 m 场比赛要进行。问联盟球队的最小总支出是多少。
在一个篮球联赛里,有 n 支球队,球队的支出是和他们的胜负场次有关系的,具体来说,第 i 支球队的赛季总支出是 Ci*x^2+Di*y^2,Di<=Ci。(赢得多,给球员的奖金就多嘛)
再接下来 m 行每行两个整数 s,t 表示第 s 支队伍和第 t 支队伍之间将有一场比赛,注意两只队间可能有多场比赛。
接下来 n 行每行 4 个整数 a[i],b[i],Ci,Di
第一行 n,m
输出总支出的最小值。
题解:一开始 naive 了,建了一个 8 层的费用流模型,把自己都吓傻了~
本题有一个不容易处理的要求,就是每场比赛只能有一队胜出,那我们不妨假设一开始所有球队的每场比赛都输了,然后我们有 m 个流量,每有一个流量流到一个队就代表这个队赢了一次,然后就很好处理了。
- #include < cstdio > #include < cstring > #include < iostream > #include < queue > using namespace std;
- int cnt,
- n,
- m,
- sum,
- mf,
- S,
- T;
- int to[1000000],
- next[1000000],
- cost[1000000],
- flow[1000000],
- pe[10000],
- pv[10000],
- head[10000],
- dis[10000];
- int A[10000],
- B[10000],
- C[10000],
- D[10000],
- E[10000],
- inq[10000];
- queue < int > q;
- int rd() {
- int ret = 0,
- f = 1;
- char gc = getchar();
- while (gc < '0' || gc > '9') {
- if (gc == ' - ') f = -f;
- gc = getchar();
- }
- while (gc >= '0' && gc <= '9') ret = ret * 10 + gc - '0',
- gc = getchar();
- return ret * f;
- }
- void add(int a, int b, int c, int d) {
- to[cnt] = b,
- cost[cnt] = c,
- flow[cnt] = d,
- next[cnt] = head[a],
- head[a] = cnt++;
- to[cnt] = a,
- cost[cnt] = -c,
- flow[cnt] = 0,
- next[cnt] = head[b],
- head[b] = cnt++;
- }
- int bfs() {
- memset(dis, 0x3f, sizeof(dis));
- int i,
- u;
- q.push(S),
- dis[S] = 0;
- while (!q.empty()) {
- u = q.front(),
- q.pop(),
- inq[u] = 0;
- for (i = head[u]; i != -1; i = next[i]) {
- if (dis[to[i]] > dis[u] + cost[i] && flow[i]) {
- dis[to[i]] = dis[u] + cost[i],
- pv[to[i]] = u,
- pe[to[i]] = i;
- if (!inq[to[i]]) q.push(to[i]),
- inq[to[i]] = 1;
- }
- }
- }
- return dis[T] < 0x3f3f3f3f;
- }
- int main() {
- n = rd(),
- m = rd();
- int i,
- j,
- a,
- b;
- S = 0,
- T = n + m + 1;
- memset(head, -1, sizeof(head));
- for (i = 1; i <= n; i++) A[i] = rd(),
- B[i] = rd(),
- C[i] = rd(),
- D[i] = rd();
- for (i = 1; i <= m; i++) a = rd(),
- b = rd(),
- E[a]++,
- E[b]++,
- add(S, n + i, 0, 1),
- add(n + i, a, 0, 1),
- add(n + i, b, 0, 1);
- for (i = 1; i <= n; i++) {
- sum += C[i] * A[i] * A[i] + D[i] * (E[i] + B[i]) * (E[i] + B[i]);
- for (j = 1; j <= E[i]; j++) add(i, T, C[i] * (2 * (A[i] + j - 1) + 1) - D[i] * (2 * (B[i] + E[i] - j) + 1), 1);
- }
- while (bfs()) {
- mf = 1 << 30;
- for (i = T; i != S; i = pv[i]) mf = min(mf, flow[pe[i]]);
- sum += mf * dis[T];
- for (i = T; i != S; i = pv[i]) flow[pe[i]] -= mf,
- flow[pe[i] ^ 1] += mf;
- }
- printf("%d", sum);
- return 0;
- }
【BZOJ1449/2895】[JSOI2009] 球队收益 / 球队预算 最小费用最大流
来源: http://www.bubuko.com/infodetail-2117396.html