[Nowcoder283F] 出装方案 (状压DP or 费用流)

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

题目链接：https://ac.nowcoder.com/acm/contest/283/F

众所周知，在各种对抗类游戏里装备都是很重要的一环，不同的出装方案会给玩家带来不同的强度。

dalao手里有N件装备，现在dalao要把装备分给N个队友，每个队友只能分一件装备，而每个队友穿上不同的装备会有不同程度的强度提升。

现在给出每个队友对每件装备的强度提升的值，请问dalao的所有分配方案里，最多能让团队的总强度提升多少呢？

这题可以DP也可以费用流。

DP可以维护$f(i,st)$表示处理到前$i$个人，并且当前已经拿了$st$个装备时的最佳方案，转移就从$st$中未标记的转移就可以。由于只和上一层的状态有关，因此存储空间可以压下。

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 16;
int f[2][1<<maxn];
int a[maxn][maxn];
int n;

int main() {
  // freopen("in", "r", stdin);
  int T;
  scanf("%d", &T);
  while(T--) {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        scanf("%d", &a[i][j]);
      }
    }
    memset(f, 0, sizeof(f));
    int nn = 1 << n;
    for(int i = 0; i < n; i++) {
      f[0][1<<i] = a[0][i];
    }
    for(int i = 1; i < n; i++) {
      for(int j = 0; j < n; j++) {
        for(int st = 1; st < nn; st++) {
          if((1 << j) & st) continue;
          f[i&1][st|(1<<j)] = max(f[i&1][st|(1<<j)], f[!(i&1)][st]+a[i][j]);
        }
      }
    }
    printf("%d\n", f[(n-1)&1][nn-1]);
  }
  return 0;
}

费用流也十分好想，一边是装备一边是人，超级源连装备费用为0容量为1，人连超级汇费用为0容量为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
116
117
#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 = 210;
const int maxm = 4010;
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;
int to[maxn][maxn];
 
signed main() {
  // freopen("in", "r", stdin);
  int T_T;
  scanf("%d", &T_T);
  while(T_T--) {
    scanf("%d", &n);
    init();
    S = 0, T = 2 * n + 1, N = T + 1;
    for(int i = 1; i <= n; i++) {
      adde(S, i, 1, 0);
      adde(n+i, T, 1, 0);
    }
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= n; j++) {
        scanf("%d", &to[i][j]);
        adde(i,n+j, 1, -to[i][j]);
      }
    }
    printf("%lld\n", -MinCostFlow(S, T, N));
  }
  return 0;
}