[ABC318D] General Weighted Max Matching 题解

这篇具有很好参考价值的文章主要介绍了[ABC318D] General Weighted Max Matching 题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

[ABC318D] General Weighted Max Matching 题解

题意

  给定无向有权完全图,求最大权匹配。

思路分析

  注意到 \(n \le 16\),我考虑状压 DP。

  设当前点集 \(S\) 中最大权匹配的答案是 \(f_S\),我们考虑 \(S\) 中“最后”一个点 \(p\)(这里的“最后”一个点是指,在状压表示状态的时候,最后一个 1 所代表的那个点,只需从这个点考虑就行,不需要考虑其他前面的点,因为会被更小状态考虑过)。

  我们可以从前面其他点中,选择一个点 \(q\) 和这个点匹配,也可以不匹配这个点。于是有转移方程:

\[f_S = \max(f_{S-p},f_{S-p-q}),p \in S,q \in S, p \ne q \]

  其中 \(w_{p,q}\) 代表点 \(p\) 与点 \(q\) 之间的边权。

  初始化:当 \(S\) 中没有点或只有一个点的时候 \(f_S = 0\);当 \(S\) 中有两个点 \(u,v\) 时,\(F_S = w_{u,v}\)文章来源地址https://www.toymoban.com/news/detail-691583.html

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 18;
const int S = (1<<(N+1));

LL a[N][N];
LL dp[S];
LL cnt[S];
LL n;

int count(int s)
{
	if(cnt[s] != -1)
		return cnt[s];
	int ans = 0;
	while(s>0)
	{
		ans += (s&1);
		s >>= 1;
	}
	return cnt[s] = ans;
}

LL dfs(int s)
{
	if(dp[s] != -1) return dp[s];
	if(count(s) <= 1)
	{
		dp[s] = 0;
		return 0;
	}
	if(count(s) == 2)
	{
		int idx1 = -1,idx2 = -1;
		int tmp = s,tmpidx = 0;
		while(tmp>0)
		{
			if(tmp&1)
			{
				if(idx1 == -1)
				{
					idx1 = tmpidx;
				}
				else
				{
					idx2 = idx1;
					idx1 = tmpidx;
				}
			}
			tmpidx++;
			tmp >>= 1;
		}
		dp[s] = a[idx1][idx2];
		return dp[s];
	}
	LL idxf = -1;
	LL ans = 0;
	for(int i = n-1;i >= 0;i--)
	{
		if((s&(1<<i)) > 0)
		{
			if(idxf == -1)
			{
				idxf = i;
			}
			else
			{
				ans = max(ans,a[idxf][i]+dfs(s-(1<<i)-(1<<idxf)));
			}
		}
	}
	ans = max(ans,dfs(s-(1<<idxf)));
	return dp[s] = ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
	memset(dp,-1,sizeof(dp));
	memset(cnt,-1,sizeof(cnt));
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		for(int j = i+1;j <= n;j++)
		{
			cin >> a[i-1][j-1];
			a[j-1][i-1] = a[i-1][j-1];
		}
	}
	dfs((1<<n)-1);
	cout << dp[(1<<n)-1] << "\n";
	return 0;
}

到了这里,关于[ABC318D] General Weighted Max Matching 题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • ABC341A-D题解

    这个没什么好说的,就先输出一个 1 ,再输出 n n n 个 01 就大功告成了。 要获取更多 x x x 国货币,只能用 x − 1 x - 1 x − 1 国货币换。 所以我们可以从 1 1 1 国一直换到 n n n 国,输出,结束。 你会发现, 50 0 3 2 ⋅ 1 0 8 500^32cdot10^8 50 0 3 2 ⋅ 1 0 8 ,所以可以暴力枚举高桥所在

    2024年02月19日
    浏览(33)
  • [ABC319E] Bus Stops 题解

      给定 (n) 个公交站。对于第 (i) 个公交站,在时刻 (p_i times k,k in mathbb{N}) 有一辆公交车出发,在经过 (t_i) 的时间后,到达第 (i+1) 个公交站。   在走到第一个公交车之前需要走 (X) 时刻,做到最后一个公交站之后下车以后还需要走 (Y) 时刻。   约束: (1

    2024年02月09日
    浏览(37)
  • [AGC055A] ABC Identity 题解

    给定长度为 (3n (1 le n le 2e5)) 的序列,其中字母 A,B,C 各有 (n) 个。 一个合法序列 (T) 满足以下条件: 其长度为 (3k (1 le k le n)) 。 (T_1 = T_2 = ... = T_k) (T_{k + 1} = T_{k + 2} = ... = T_{2k}) (T_{2k + 1} = T_{2k + 2} = ... = T_{3k}) (T_1, T_{k + 1}, T_{2k + 1}) 互不相同。 求一个把这个序列分

    2024年02月08日
    浏览(49)
  • [ABC347C] Ideal Holidays题解

    原题传送门 原题传送门(洛谷) ​题意翻译: ​在 (AtCoder) 王国中,一个周有 (A+B) 天。其中在一周中, ([1,A]) 天是假日, ([A+1,B]) 天是工作日。 ​高桥有 (N) 个计划,第 (i) 个计划安排在 (i) 天后。他不知道今天是周几,但他想知道是否能将计划都安排在假期中;

    2024年04月08日
    浏览(44)
  • [AGC055B] ABC Supremacy 题解

    给定两个长度为  (n)  的字符串  (a) , (b) 。 你可以进行若干次以下操作: 若  (a)  中的一个 子串 为  ABC , BCA  或  CAB ,那么可以将这个子串替换为  ABC , BCA  或  CAB 。 求能否将  (a)  变成  (b) ,输出  YES  或  NO 。 不难发现,我们可以根据一些变换将 A

    2024年02月08日
    浏览(37)
  • 题解:ABC320B - Longest Palindrome

    链接:Atcoder。 链接:洛谷。 算法难度:C。 思维难度:C。 调码难度:C。 综合评价:入门。 字符串处理。 通过双层循环分别枚举第一个字符和最后一个字符遍历每个子串,在分别判断是否为回文串,在所有是回文串的里面取长度最大值。 O(|s|2)。 字符串截取用substr函数。

    2024年02月07日
    浏览(41)
  • AtCoder abc336 A~D题解

    题目翻译: 对于正整数 X X X 级别的龙串, X X X 是长度为 ( X + 3 ) (X+3) ( X + 3 ) 的字符串,由按此顺序排列的 o 、 n 和 g 的一次 L 、 X X X 次出现形成。 你得到一个正整数 N N N 。打印 N N N 级的龙串。 分析 按题目要求做即可……,输出一个 L ,循环 X X X 次输出 o ,再输出 ng 。

    2024年01月15日
    浏览(39)
  • AT_abc344_d 题解

    本文同步发表于洛谷。 赌狗天天输的一集。 你最开始有一个空字符串 (S) 。 你还有编号为 (1, 2, dots, N) 的袋子,每个袋子都包含一些字符串。 袋子 (i) 包含 (A_i) 个字符串 (S_{i,1}, S_{i,2}, dots, S_{i,A_i}) 。 对 (i = 1, 2, dots, N) 重复以下步骤 仅一次 (这里原题没有讲清楚

    2024年03月10日
    浏览(50)
  • AT_abc345_d 题解

    本文同步发表于洛谷。 是个逆天搜索。 最开始:爆搜,启动! 然后 TLE 到飞起。 赛后:我【数据删除】这么简单的吗?! dfs 每个位置,试着把没放过的块放到以这个位置为左上角的区域里面。 好了没了,就是这么简单! 对了记得这个块可以旋转!

    2024年03月21日
    浏览(44)
  • AT_abc344_e 题解

    本文同步发表于洛谷。 赌狗天天输的一集。 赛时各种【数据删除】原因导致没做出来。 给你一个长度为 (N) 的序列 (A=(A_1,ldots,A_N)) 。保证 (A) 中的元素是不同的。 你要处理 (Q) 个操作。每个操作是以下两种类型之一: 1 x y :在 (A) 中元素 (x) 后面紧接着插入 (y) 。

    2024年03月13日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包