取数游戏：最大总得分算法及C++实现

题目描述

给出一个 'n × n' 的矩阵，进行取数游戏。取数共 'n' 轮，第 'i' 轮需要从每行分别取一个没取过的数字，设取出的数字总和是 's'，则第 'i' 轮的实际得分是 'i × s'。求 'n' 轮取数的最大总得分。

输入格式

从标准输入读入数据。第一行输入一个正整数 'n' ('n ≤ 100')。接下来 'n' 行，每行输入 'n' 个正整数 'a_{ij}' ('a_{ij} ≤ 10^6')，构成一个矩阵。

输出格式

输出到标准输出。输出一个整数，表示最大总得分。

样例 #1

样例输入 #1

样例输出 #1

算法思路

本题可以用二分图匹配来解决。我们将矩阵的行和列分别看作二分图的左右两部分，每个数字 'a_{ij}' 代表左部节点 'i' 和右部节点 'j' 之间的边，边的权值为 'a_{ij}'。

对于每一轮取数，我们实际上需要找到一个匹配，使得从左部每个节点都有一条边连接到右部的一个节点，且所有边权之和最大。

为了计算最大总得分，我们对每一轮取数都进行一次二分图匹配，然后将每轮的得分累加起来即可。

C++ 代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
struct edge {
    int ver, nxt, val;
} e[N * 2];
int head[N], cnt = 1;
void add(int u, int v, int w) {
    e[++cnt] = (edge){v, head[u], w};
    head[u] = cnt;
}
int n;
int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * w;
}
int a[110][110];
int match[N], vis[N];
int dfs(int u, int fa) {
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].ver;
        if (v == fa || vis[v]) continue;
        vis[v] = 1;
        if (!match[v] || dfs(match[v], u)) {
            match[v] = u;
            return 1;
        }
    }
    return 0;
}
int main() {
    n = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = read();
    long long ans = 0;
    for (int k = 1; k <= n; k++) {
        memset(match, 0, sizeof(match));
        memset(head, 0, sizeof(head));
        cnt = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i == k || j == k) add(i, j, a[i][j]);
        for (int i = 1; i <= n; i++) {
            memset(vis, 0, sizeof(vis));
            if (dfs(i, 0)) ans += k * a[i][match[i]];
        }
    }
    printf("%lld", ans);
    return 0;
}

代码解释

结构体定义: edge 结构体用于存储二分图中的边，包含节点编号 ver、下一个边节点 nxt 和边权 val。
邻接表: 使用 head 数组和 e 数组构建邻接表，方便存储每个节点的相邻节点。
输入数据: 读取矩阵的行列数 'n' 和矩阵中的数字 'a_{ij}'。
二分图匹配: 使用 match 数组记录每个右部节点匹配的左部节点，使用 vis 数组标记每个节点是否已经被访问。
DFS 深度优先搜索: 使用 DFS 算法进行二分图匹配，从左部每个节点开始搜索，找到一条匹配路径。
计算得分: 对于每轮取数，将匹配到的所有边权累加起来，并乘以当前轮数，得到当前轮的得分。
累加得分: 将每一轮的得分累加起来，得到最终的最大总得分。

总结

本题使用二分图匹配求解最大总得分，算法简洁高效。通过C++代码实现，可以快速解决问题。

希望以上内容对您有所帮助！