HDU 3995 Special Fish(KM最大匹配)

2024-06-01 19:08

本文主要是介绍HDU 3995 Special Fish(KM最大匹配),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

HDU 3995 Special Fish

题目链接

题意:一些鱼,每只鱼都有一个权值,给一个矩阵,如果mat[i][j] = 1表示i会攻击j,每只鱼可以攻击一次和被攻击一次,每次攻击可以得到权值为val[i]^val[j],问最大能得到多少权值

思路:KM最大匹配,每个鱼拆成攻击和被攻击两边,然后连边跑KM最大匹配即可

代码:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;const int MAXNODE = 105;typedef int Type;
const Type INF = 0x3f3f3f3f;struct KM {int n, m;Type g[MAXNODE][MAXNODE];Type Lx[MAXNODE], Ly[MAXNODE], slack[MAXNODE];int left[MAXNODE], right[MAXNODE];bool S[MAXNODE], T[MAXNODE];void init(int n, int m) {this->n = n;this->m = m;memset(g, 0, sizeof(g));}void add_Edge(int u, int v, Type val) {g[u][v] = val;}bool dfs(int i) {S[i] = true;for (int j = 0; j < m; j++) {if (T[j]) continue;Type tmp = Lx[i] + Ly[j] - g[i][j];if (!tmp) {T[j] = true;if (left[j] == -1 || dfs(left[j])) {left[j] = i;right[i] = j;return true;}} else slack[j] = min(slack[j], tmp);}return false;}void update() {Type a = INF;for (int i = 0; i < m; i++)if (!T[i]) a = min(a, slack[i]);for (int i = 0; i < n; i++)if (S[i]) Lx[i] -= a;for (int i = 0; i < m; i++)if (T[i]) Ly[i] += a;}Type km() {memset(left, -1, sizeof(left));memset(right, -1, sizeof(right));memset(Ly, 0, sizeof(Ly));for (int i = 0; i < n; i++) {Lx[i] = -INF;for (int j = 0; j < m; j++)Lx[i] = max(Lx[i], g[i][j]);}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) slack[j] = INF;while (1) {memset(S, false, sizeof(S));memset(T, false, sizeof(T));if (dfs(i)) break;else update();}}Type ans = 0;for (int i = 0; i < n; i++)ans += g[i][right[i]];return ans;}
} gao;const int N = 105;int n, val[N];
char str[N];int main() {while (~scanf("%d", &n) && n) {gao.init(n, n);for (int i = 0; i < n; i++) scanf("%d", &val[i]);for (int i = 0; i < n; i++) {scanf("%s", str);for (int j = 0; j < n; j++) {if (str[j] == '1') {gao.add_Edge(i, j, val[i]^val[j]);}}}printf("%d\n", gao.km());}return 0;
}


这篇关于HDU 3995 Special Fish(KM最大匹配)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1021869

相关文章

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式?IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地

浅谈配置MMCV环境,解决报错,版本不匹配问题

《浅谈配置MMCV环境,解决报错,版本不匹配问题》:本文主要介绍浅谈配置MMCV环境,解决报错,版本不匹配问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录配置MMCV环境,解决报错,版本不匹配错误示例正确示例总结配置MMCV环境,解决报错,版本不匹配在col

详解nginx 中location和 proxy_pass的匹配规则

《详解nginx中location和proxy_pass的匹配规则》location是Nginx中用来匹配客户端请求URI的指令,决定如何处理特定路径的请求,它定义了请求的路由规则,后续的配置(如... 目录location 的作用语法示例:location /www.chinasem.cntestproxy

Nginx中location实现多条件匹配的方法详解

《Nginx中location实现多条件匹配的方法详解》在Nginx中,location指令用于匹配请求的URI,虽然location本身是基于单一匹配规则的,但可以通过多种方式实现多个条件的匹配逻辑... 目录1. 概述2. 实现多条件匹配的方式2.1 使用多个 location 块2.2 使用正则表达式

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中,括号匹配是一个常见问题,尤其是在

关于Gateway路由匹配规则解读

《关于Gateway路由匹配规则解读》本文详细介绍了SpringCloudGateway的路由匹配规则,包括基本概念、常用属性、实际应用以及注意事项,路由匹配规则决定了请求如何被转发到目标服务,是Ga... 目录Gateway路由匹配规则一、基本概念二、常用属性三、实际应用四、注意事项总结Gateway路由

如何提高Redis服务器的最大打开文件数限制

《如何提高Redis服务器的最大打开文件数限制》文章讨论了如何提高Redis服务器的最大打开文件数限制,以支持高并发服务,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录如何提高Redis服务器的最大打开文件数限制问题诊断解决步骤1. 修改系统级别的限制2. 为Redis进程特别设置限制