首页 > 其他分享 >[题解] BZOJ4203 同桌的你

[题解] BZOJ4203 同桌的你

时间:2024-03-26 12:11:24浏览次数:38  
标签:rt pre int 题解 同桌 BZOJ4203 max push dp

题意

给出 \(n\) 个人的性别 \(b_i\)、喜欢的人 \(a_i\)(有且仅有一个)。
现在两人分一组,若一组中存在一人喜欢另一人,则称这一组为「满意」的。
要求在最大化「满意」组数的前提下最大化男女同桌组数,并构造分组方案。

思路

考虑建图,从 \(i\) 到 \(a_i\) 连一条有向边,转化为基环树上最大匹配。
我们任选一条环上的边,将它删去,跑一遍树上DP。唯一可能比它优的情况是保留这条边,删去一条与它相邻的环边。所以跑两次DP取最优值即可。
正确性:如果当前删除的这条边在最优解里面,那么与它相邻的环边一定不在最优解里面。

  • 找环:发现这是一棵基环内向树,任何一个点沿着唯一出边走都会走到环上,可以随便选一个点直接循环找到。

  • 拆边DP:建反图,这样可以保证对于任意点,它唯一的入边来自它的父亲,方便转移。

令 \(dp_{u,1/0}\) 表示以 \(u\) 为根节点的子树中,\(u\)被/不被匹配时能获得的最大价值,\(dp_{u,0}\) 显然为 \(u\) 各子树最大价值之和,\(dp_{u,1}\) 则需要钦定一个子节点 \(v\) 与 \(u\) 匹配,单独算 \(v\) 的贡献。于是有:

\[dp_{u,0} = \sum\limits_{v \in son_u}{\max(dp_{v,0}, dp_{v,1})} \]

\[dp_{u,1} = \max\limits_{v \in son_u}{(dp_{u,0}-\max(dp_{v,0}, dp_{v,1})+dp_{v, }+val(u,v))} \]

处理一组匹配的贡献 \(val(u,v)\) 大致有两种做法:

  1. 把「满意」组数、男女同桌组数装在结构体里,重载比较、合并的运算符。
  2. 令贡献为首要权值乘一个基数 \(B\) 再加上次要权值(\(B\) 大于次要权值值域即可),最终答案分别为 \(\left\lfloor\dfrac{ans}{B}\right\rfloor\)、\(ans \bmod B\)。

我用的是第二种。构造方案就记录每个状态从哪里转移来即可,注意这道题DFS可能会爆栈。

Code

#include <bits/stdc++.h>
#define IL inline
#define vec basic_string
#define QAQ pair<ll, vec<Node_t>>
using namespace std;
using ll = long long;

const int N = 1e6 + 5, B = 1e9;

vector<int> g[N];
int a[N], b[N], vis[N], pre[N]; ll dp[N][2];
struct Node_t {
	int first, second;
	IL bool operator<(const Node_t &o) const {
		return first == o.first ? second < o.second : first < o.first;
	}
};

IL QAQ bfs(int rt) {
	queue<int> q; q.push(rt);
	vec<int> Q; Q.push_back(rt);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v : g[u]) if (v != rt) q.push(v), Q.push_back(v);
	}
	for (int i = Q.size() - 1; i >= 0; i--) {
		int u = Q[i];
		vis[u] = 1, dp[u][0] = dp[u][1] = pre[u] = 0;
		for (int v : g[u]) if (v != rt) dp[u][0] += max(dp[v][0], dp[v][1]);
		for (int v : g[u]) if (v != rt) {
			ll _ = dp[u][0] - max(dp[v][0], dp[v][1]) + dp[v][0] + B + (b[u] != b[v]);
			if (_ > dp[u][1]) dp[u][1] = _, pre[u] = v;
		}
	}
	vec<Node_t> res;
	for (int u : Q) if (dp[u][1] > dp[u][0] && pre[u]) res.push_back({u, pre[u]}), pre[pre[u]] = 0;
	return {max(dp[rt][0], dp[rt][1]), res};
}
IL QAQ operator+(const QAQ & a, const QAQ & b) {
	return {a.first + b.first, a.second + b.second};
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i] >> b[i], g[a[i]].push_back(i);
		}
		QAQ ans;
		for (int i = 1, p, q; i <= n; i++) if (!vis[i]) {
			p = i; while (!vis[a[p]]) vis[p] = 1, p = a[p]; q = a[p];
			ans = ans + max(bfs(p), bfs(q));
		}
		cout << ans.first / B << ' ' << ans.first % B << '\n';
		for (auto & p : ans.second) cout << p.first << ' ' << p.second << '\n';
		for (int i = 1; i <= n; i++) g[i].clear(), vis[i] = 0;
	}
	return 0;
}

P1352 没有上司的舞会:树上最大独立集
Vijos1144 小胖守皇宫:树上最小支配集
P8655 [蓝桥杯 2017 国 B] 发现环:基环树找环板子,可用 tarjan / 并查集 / 拓扑排序
P9869 [NOIP2023] 三值逻辑:建图 + 找环
P1453 城市环路:基环树拆边DP板题
P2607 [ZJOI2008] 骑士:P1453双倍经验
P3651 展翅翱翔之时 (はばたきのとき):基环树上贪心
P4381 [IOI2008] Island:基环树森林直径之和

reference:

基环树学习指南 —— White_Sheep
P9869 | 你真的会基环树找环吗 —— Moeebius
[题解]P4381 [IOI2008]Island —— marTixx

标签:rt,pre,int,题解,同桌,BZOJ4203,max,push,dp
From: https://www.cnblogs.com/wkh2008/p/18096365

相关文章

  • AGC018C Coins 题解
    模拟费用流。传送门题意:共\(n=x+y+z\)个人,每个人可以选择获得\(a_i\)个金币或\(b_i\)个银币或\(c_i\)个铜币。要选\(x\)个人拿金币,\(y\)个人拿银币,\(z\)个人拿铜币。问币数总和最大是多少。\(n\le10^5\)。先建出费用流模型:把一个人的选择视作一个人流到了金币/......
  • Atcoder ABC 346 全题解
    闲话上一篇全题解反向不错,如果大家支持我就会继续更。我ABC也打了,ARC也打了,没打好,疯狂掉大分……包括本场比赛也是整整补了EFG三道题,以及ARC死磕D结果使赛后五分钟AC又有素材了……A懒得讲B由于我被B题坑了,所以在此纪念。最简单的方法就是把字符串复制......
  • 20240325每日一题题解
    20240325每日一题题解Problem给出一个整数\(a\)和一个正整数\(n\),求乘方\(a^n\)。输入一行,包含两个整数\(a\)和\(n\)。\(-1000000\lea\le1000000\),\(1\len\le10000\)。输出一个整数,即乘方结果。题目保证最终结果的绝对值不超过\(1000000\)。样例输入23样......
  • 动态尺寸加载libpag文件白边问题解决方案
    加载pag文件时,最理想的情况是canvas的宽高和pag资源文件的宽高一致,或比例一致。否则就会出现四周白边(页面底色),除非是按平铺的样式进行设置(源码暂未找到对应方法)。而对于页面宽高不定的情况下,就无法保证pag文件能适配页面,如果pag文件底色和父级页面底色不一致,就会表现出来......
  • CSP-S 2023 题解
    T1听说有歧义?希卓没看懂。不过真的水。你看能把它拧成什么正确密码。#include<bits/stdc++.h>#defineLLlonglongusingnamespacestd;LLn,sum,a[10][6],p,b[10][6];LLf[100010];intmain(){ scanf("%lld",&n); for(inti=1;i<=n;i++) { for(intj=1;j<=5;j++)......
  • CSP-J 2023 题解
    T1这么水?!赛时AC。思路:小学数学题,我孙子都会做认真点。就是余数和商,小学二年级的知识(毕导:亻尔女子)代码:#include<bits/stdc++.h>#defineLLlonglongusingnamespacestd;LLn,sum;LLt(LLa){ if(a!=1)return1+t(a-((a-1)/3+1)); elsereturn1;}intmain(){......
  • AT_arc175_a [ARC175A] Spoon Taking Problem 题解
    题目翻译link有\(N\)人围坐在一张圆桌旁,按逆时针顺序编号为\(1\)至\(N\)。每个人都有一个惯用手圆桌上有\(N\)把勺子,编号为\(1\)到\(N\),每对相邻的人之间放一把勺子给你一个\((1,\dots,N)\)的排列组合\((P_1,\dots,P_N)\)。在\(i=1,\dots,N\)的顺序中,人......
  • 题解:AT_abc345_c [ABC345C] One Time Swap
    求过审题面翻译给定一个字符串$s$,求执行以下操作一次可以产生的字符串的个数设$N$为$s$的长度。选择一对整数$(i,j)$,使$1≤i<j≤N$,交换$s$的第$i$个和第$j$个字符可以证明,在这个问题的约束条件下,你总是可以得到它思路暴力做法我们可以......
  • JavaScript:void(0) 用法及常见问题解析
    JavaScript:void(0)用法及常见问题解析javascript:void(0);是一种在JavaScript和网页开发中经常使用的技术,尤其在处理链接的行为时。本文将深入探讨javascript:void(0);的用法,以及在使用过程中可能遇到的常见问题和解决方法。什么是javascript:void(0);?javascript:v......
  • LeetCode第390场周赛题解(c++)
    真的无语了,早上怎么都提交不了,显示未知错误。。。结果晚上就可以提交了。唉100245.每个字符最多出现两次的最长子字符串给你一个字符串 s ,请找出满足每个字符最多出现两次的最长子字符串,并返回该子字符串的 最大 长度。示例1:输入: s="bcbbbcba"输出: 4解释:以......