博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU 2426 Interesting Housing Problem
阅读量:7013 次
发布时间:2019-06-28

本文共 2272 字,大约阅读时间需要 7 分钟。

HDU_2426

这个题目是一个求最大权完美匹配的题目,我们需要注意两点:一、要处理好负边的情况。二、要注意NM不一定相等。

对于第一点的处理,我见过的有两种处理方式:①将所有边都初始化成负边,这样当做N-M之间所有的边都是存在的去进行匹配,如果最后发现边权为正的匹配数为N的话就是有解的,否则无解。②将为负值的边视为不存在,并且在KM算法过程中,如果发现当前状态不能再进行增广,则无解。

对于第二点的处理,我见过的有些AC的程序也没有注意到这个问题,如果对这一点不加处理的话,如果出现N>M的数据并且是用第①种方式去处理第一点的话,程序会陷入死循环。

另外,这个题让我不解的是,现在网上可以搜到的KM算法的slack优化有两种形式,一种是数组形式的,一种是单一变量形式的,我并不觉得两个形式有什么本质的不同,同时我觉得数组形式的应该理论上效率还要稍低一些,但是我用单一变量形式写出的程序(采用第②种方式处理第一点,因为采用第①种方式处理会更慢)要跑1200ms左右,而我搜到的用数组形式写的程序(采用第①种方式处理第一点,采用第②种方式处理要相对慢很多)只跑不到400ms,这个很让我不解。

#include
#include
#define MAXD 510 #define INF 1000000000 int N, M, E, G[MAXD][MAXD]; int yM[MAXD], A[MAXD], B[MAXD]; int visx[MAXD], visy[MAXD], slack; void init() {
int i, s, r, v; memset(G, -1, sizeof(G)); for(i = 0; i < E; i ++) {
scanf("%d%d%d", &s, &r, &v); if(G[s][r] == -1 || v > G[s][r]) G[s][r] = v; } } int searchpath(int u) {
int v, temp; visx[u] = 1; for(v = 0; v < M; v ++) if(G[u][v] != -1 && !visy[v]) {
temp = A[u] + B[v] - G[u][v]; if(temp == 0) {
visy[v] = 1; if(yM[v] == -1 || searchpath(yM[v])) {
yM[v] = u; return 1; } } else if(temp < slack) slack = temp; } return 0; } int EK() {
int i, j, u, v; for(i = 0; i < N; i ++) {
A[i] = -1; for(j = 0; j < M; j ++) if(G[i][j] > A[i]) A[i] = G[i][j]; } memset(B, 0, sizeof(B)); memset(yM, -1, sizeof(yM)); for(u = 0; u < N; u ++) {
for(;;) {
slack = INF; memset(visx, 0, sizeof(visx)); memset(visy, 0, sizeof(visy)); if(searchpath(u)) break; if(slack == INF) return 0; for(i = 0; i < N; i ++) if(visx[i]) A[i] -= slack; for(i = 0; i < M; i ++) if(visy[i]) B[i] += slack; } } return 1; } void printresult() {
int i, res = 0; for(i = 0; i < M; i ++) if(yM[i] != -1) res += G[yM[i]][i]; printf("%d\n", res); } int main() {
int t = 0; while(scanf("%d%d%d", &N, &M, &E) == 3) {
init(); printf("Case %d: ", ++t); if(EK()) printresult(); else printf("-1\n"); } return 0; }

转载地址:http://esqtl.baihongyu.com/

你可能感兴趣的文章
聊聊springcloud的GatewayControllerEndpoint
查看>>
聊聊sentinel的SentinelResourceAspect
查看>>
聊聊flink的SpoutWrapper
查看>>
聊聊flink的StateDescriptor
查看>>
git 使用教程,常用命令
查看>>
Android view事件分发初步
查看>>
使用SVI实现Vlan间路由
查看>>
Linux学习笔记5月28日任务
查看>>
解决Td内容为空时不显示边框的问题-兼容IE、firefox、chrome
查看>>
SylixOS x86中断探测(二)
查看>>
HDFS总结
查看>>
scala 中导出excel
查看>>
悬浮框保证在中间js
查看>>
Nginx负载均衡算法
查看>>
Linux的目录结构
查看>>
linux基础命令
查看>>
Nginx服务器
查看>>
7月技术指标
查看>>
各个数据库的扩展名/格式/后缀
查看>>
入门一班 20181015 shell 特殊命令
查看>>