[Nowcoder208A] Birthday(最小费用最大流)

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：https://www.nowcoder.com/acm/contest/206/A

题意很简单，给你n个球，m个桶。现在每个球最多可以丢到两个桶中的一个，同时规定每个桶中球的平方和为代价。现在希望你找一个方案，使得代价最小。

一开始random_shuffle后回溯在60%左右T掉。。

回溯的时候往一个当前有$x$个球的桶里丢一个球的时候，代价的增幅为$(x+1)^2-x^2$，于是来了灵感。

我们可以把丢球的过程看作节点，每次往一个当前有$x$个球的桶里多丢一个球的时候，意味着代价增加了$(x+1)^2-x^2$，而且这个代价是单调递增的。

我们考虑建图，超级源、汇中间有n个代表球的节点和m个代表桶中球数量的节点：

由源点出发，n个节点代表球，各连接一条，流量为1，费用为0的边。

接着从n个节点向m个节点出发，代表球可以向某两个桶里丢，流量为1，费用为0。

接着由m个桶向汇点连边，每个桶连n条边，流量为1，费用为该桶+1个球后代价的涨幅。由于涨幅是递增的，因此在求最小费用最大流的时候肯定从小到大流。

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef struct Node {
  int u, v, next;
  LL c, w;
}Node;
const int maxn = 7070;
const int maxm = 20010;
const LL mod = 0x3f3f3f3fLL;
const LL inf = (1LL<<55);
int tot, head[maxn];
LL dist[maxn];
LL cost, flow;
Node e[maxm];
int pre[maxn];
bool visit[maxn];
queue<int> Q;
int S, T, N;

void init() {
  S = T = N = 0;
  memset(head, -1, sizeof(head));
  tot = 0;
}
// c:容量, w:费用
void adde(int u, int v, LL c, LL w) {
  e[tot].u = u; e[tot].v = v; e[tot].c = c; e[tot].w = w; e[tot].next = head[u]; head[u] = tot++;
  e[tot].u = v; e[tot].v = u; e[tot].c = 0; e[tot].w = -w; e[tot].next = head[v]; head[v] = tot++;
}
bool spfa(int s, int t, int n) {
  int i;
  for(i = 0; i <= n; i++) {
    dist[i] = inf;
    visit[i] = 0;
    pre[i] = -1;
  }
  while(!Q.empty()) Q.pop();
  Q.push(s);
  visit[s] = true;
  dist[s] = 0;
  pre[s] = -1;
  while(!Q.empty()) {
    int u = Q.front();
    visit[u] = false;
    Q.pop();
    for(int j = head[u]; j != -1; j = e[j].next) {
      if(e[j].c > 0 && dist[u] + e[j].w < dist[e[j].v]) {
        dist[e[j].v] = dist[u] + e[j].w;
        pre[e[j].v] = j;
        if(!visit[e[j].v]) {
          Q.push(e[j].v);
          visit[e[j].v] = true;
        }
      }
    }
  }
  // return dist[t] < 0; // 求可行流
  if(dist[t] == inf) return false;  // 求最小费用流
  else return true;
}
LL ChangeFlow(int t) {
  LL det = mod;
  int u = t;
  while(~pre[u]) {
    u = pre[u];
    det = min(det, e[u].c);
    u = e[u].u;
  }
  u = t;
  while(~pre[u]) {
    u = pre[u];
    e[u].c -= det;
    e[u ^ 1].c += det;
    u = e[u].u;
  }
  return det;
}
LL MinCostFlow(int s, int t, int n) {
  LL mincost, maxflow;
  mincost = maxflow = 0;
  while(spfa(s, t, n)) {
    LL det = ChangeFlow(t);
    mincost += det * dist[t];
    maxflow += det;
  }
  cost = mincost;
  flow = maxflow;
  return mincost;
}

int n, m;

signed main() {
  // freopen("in", "r", stdin);
  int a, b;
  while(~scanf("%d%d",&n,&m)) {
    init();
    S = 0, T = n + m + 1; N = T + 1;
    for(int i = 1; i <= n; i++) adde(S, i, 1, 0);
    for(int i = 1; i <= n; i++) {
      scanf("%d%d",&a,&b);
      adde(i, n+a, 1, 0);
      adde(i, n+b, 1, 0);
    }
    for(int i = 1; i <= m; i++) {
      for(int j = 1; j <= n; j++){
        adde(i+n, T, 1, j*j-(j-1)*(j-1));
      }
    }
    printf("%lld\n", MinCostFlow(S, T, N));
  }
  return 0;
}