“东信杯”广西大学第一届程序设计竞赛（同步赛）F 出装方案【KM 最大权值匹配】

传送门：https://ac.nowcoder.com/acm/contest/283/F

题目描述

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

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

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

输入描述:

第一行有一个整数T，表示数据的组数（不会超过150组）

每组数据第一行包含一个整数N，接下来会有N行，每行有N个整数，其中第 a 行的第 b 个数字表示第 a 个队友穿上第 b 件装备的强度提升。任何队员穿任何装备的强度提升都不会超过20000。

$1 \leq N \leq 15$

输出描述:

对于每组数据在一行内输出一个整数表示强度能够提升的最大值

示例1

输入

复制

2
4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 3 5
2 4 6
7 9 11

输出

复制

34
16

题意概括：如题

解题思路：

呵呵，KM 最大权值匹配。

赛后怒A的一题，这里留下记录嘲讽自己，警醒自己。当时在玩蛇呢！！！

AC code：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cmath>
 5 #define INF 0x3f3f3f3f
 6 #define LL long long
 7 using namespace std;
 8 const int MAXN = 310;
 9 int N, nx, ny;
10 int linker[MAXN], lx[MAXN], ly[MAXN], slack[MAXN];
11 int visx[MAXN], visy[MAXN], w[MAXN][MAXN];
12 
13 int Find(int x)
14 {
15     visx[x] = true;
16     for(int y = 1; y <= ny; y++){
17         if(visy[y]) continue;
18         int ttp = lx[x] + ly[y] -w[x][y];
19         if(ttp == 0){
20             visy[y] = true;
21             if(linker[y] == -1 || Find(linker[y])){
22                 linker[y] = x;
23                 return true;
24             }
25         }
26         else if(slack[y] > ttp) slack[y] = ttp;
27     }
28     return false;
29 }
30 
31 int KM()
32 {
33     memset(linker, -1, sizeof(linker));
34     memset(ly, 0, sizeof(ly));
35     for(int i = 1; i <= nx; i++){
36         lx[i] = -INF;
37         for(int j = 1; j <= ny; j++)
38             if(w[i][j] > lx[i]) lx[i] = w[i][j];
39     }
40 
41     for(int x = 1; x <= nx; x++){
42         for(int i = 1; i <= ny; i++){
43             slack[i] = INF;
44         }
45         while(1){
46             memset(visx, false, sizeof(visx));
47             memset(visy, false, sizeof(visy));
48             if(Find(x)) break;
49 
50             int d = INF;
51             for(int i = 1; i <= ny; i++)
52                 if(!visy[i] && d > slack[i])
53                     d = slack[i];
54             for(int i  = 1; i <= nx; i++)
55                 if(visx[i]) lx[i]-=d;
56             for(int j = 1; j <= ny; j++)
57                 if(visy[j]) ly[j]+=d;
58                 else slack[j]-=d;
59         }
60     }
61     int res = 0;
62     for(int i = 1; i <= ny; i++)
63         if(linker[i] > -1)
64         res+=w[linker[i]][i];
65     return res;
66 }
67 
68 int main()
69 {
70     int T_case;
71     scanf("%d", &T_case);
72     while(T_case--){
73         scanf("%d", &N);
74         nx = ny = N;
75         for(int i = 1; i <= N; i++)
76         for(int j = 1; j <= N; j++){
77             scanf("%d", &w[i][j]);
78         }
79         int ans = KM();
80         printf("%d
", ans);
81     }
82 }

View Code

“东信杯”广西大学第一届程序设计竞赛（同步赛）F 出装方案 【KM 最大权值匹配】