博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
ZOJ-2362 Beloved Sons 最大权值匹配
阅读量:5875 次
发布时间:2019-06-19

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

题意:国王有N个儿子,现在每个儿子结婚都能够获得一定的喜悦值,王子编号为1-N,有N个女孩的编号同样为1-N,每个王子心中都有心仪的女孩,现在问如果安排,能够使得题中给定的式子和最大。

分析:其实题目中那个开根号是个烟雾弹,只要关心喜悦值的平方即可。那么对王子和女孩之间构边,边权为喜悦值的平方,对于每一个王子虚拟出一个女孩边权为0,这样是为了所有的王子都能够有女孩可以配对,以便算法能够正确的执行。

#include 
#include
#include
#include
#include
using namespace std;const int N = 405;const int inf = 0x3f3f3f3f;int n, m;int like[N];int w[N][N<<1];int match[N<<1];int lx[N], ly[N<<1], slack[N<<1];int vx[N], vy[N<<1];int marry[N];bool path(int u) { vx[u] = 1; for (int v = 1; v <= m; ++v) { if (vy[v] || w[u][v] == -1) continue; int t = lx[u]+ly[v]-w[u][v]; if (!t) { vy[v] = 1; if (!match[v] || path(match[v])) { match[v] = u; return true; } } else { slack[v] = min(slack[v], t); } } return false;}void KM() { memset(lx, 0x80, sizeof (lx)); memset(ly, 0, sizeof (ly)); memset(match, 0, sizeof (match)); memset(marry, 0, sizeof (marry)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (w[i][j] != -1) { lx[i] = max(lx[i], w[i][j]); } } } for (int i = 1; i <= n; ++i) { memset(slack, 0x3f, sizeof (slack)); while (1) { memset(vx, 0, sizeof (vx)); memset(vy, 0, sizeof (vy)); if (path(i)) break; int d = inf; for (int j = 1; j <= m; ++j) { if (!vy[j]) d = min(d, slack[j]); } if (d == inf) break; for (int j = 1; j <= n; ++j) { if (vx[j]) lx[j] -= d; } for (int j = 1; j <= m; ++j) { if (vy[j]) ly[j] += d; else slack[j] -= d; } } } for (int i = 1; i <= m; ++i) { if (match[i] && i <= n) { marry[match[i]] = i; } } for (int i = 1; i <= n; ++i) { printf(i == 1 ? "%d" : " %d", marry[i]); } puts("");}int main() { int T; scanf("%d", &T); while (T--) { memset(w, 0xff, sizeof (w)); scanf("%d", &n); m = n << 1; for (int i = 1; i <= n; ++i) { scanf("%d", &like[i]); } int x, y; for (int i = 1; i <= n; ++i) { scanf("%d", &x); for (int j = 0; j < x; ++j) { scanf("%d", &y); w[i][y] = like[i] * like[i]; } w[i][n+i] = 0; } KM(); } return 0;}

 

转载于:https://www.cnblogs.com/Lyush/p/3204767.html

你可能感兴趣的文章
react源码ReactTreeTraversal.js之数据结构与算法
查看>>
mysql锁(Innodb)
查看>>
一致性 Hash 算法的实际应用
查看>>
css3动画
查看>>
设计模式的知识大纲分享
查看>>
PHP 命令行方式实现异步多进程模式的任务处理
查看>>
React Fiber知识点学习笔记
查看>>
「DigitalOcean Droplet」 Server Overview
查看>>
腾讯 Tars-Go 服务 Hello World——从 HTTP 开始
查看>>
java重入锁、公平锁和非公平锁
查看>>
webpack4系列教程(二):创建项目,打包第一个JS文件
查看>>
JSONP跨域请求学习
查看>>
javascript面向对象之继承(上)
查看>>
[LeetCode] 947. Most Nodes Removed
查看>>
自学 Java 怎么入门?
查看>>
网狐荣耀6701/6801 手机打包发布
查看>>
javascript单例、代理、状态设计模式
查看>>
深度解析React以create-react-app为基础创建项目
查看>>
Framework 核心服务之 PackageManagerService 钻研(4)- PackageInstaller
查看>>
SQLServer之创建DML AFTER UPDATE触发器
查看>>