首页 > 其他分享 >线性代数题解

线性代数题解

时间:2023-12-06 14:33:36浏览次数:44  
标签:UU 题解 行和列 最小 贡献 线性代数

前言

写完了这道题我好想刚明白一点最小割???UU好闪,拜谢UU。

题解

首先,我们可以发现若第 \(i\) 行的 \(B\) 没选,那么第 \(i\) 列的 \(B\) 也不选,所以此时对于行和列是等价的。

若 \(A_i\) 是 \(0\),则会减少贡献 \(\sum_{j}B_{i, j}\)。否则会减少贡献 \(C_i\)。当 \(A_i\) 是 \(0\) 但 \(A_j\) 是 \(1\) 的时候,我们会减少贡献 \(B_{j, i}\) 的贡献。所以就可以建模了。

如下图

其中位于 \(S\) 区域的行和列表示 \(A\) 为 \(1\),会选上;\(T\) 区域的行和列表示 \(A\) 为 \(0\),不会选上。

主要的精华是:最小割所割出的容量是当前不同的点属于 \(S,T\) 集合状态下我们的花费。图中的最大流只在求最小割的时候用到了,没有实际的意义。

标签:UU,题解,行和列,最小,贡献,线性代数
From: https://www.cnblogs.com/jueqingfeng/p/17879481.html

相关文章

  • CF603题解
    CF603CodeforcesRound334(Div.1)CF603AlinkCF603A题意现有一个长度为\(n\)的01串,可以进行一次区间翻转(起点终点随意,并且区间里的值1变0,0变1),得到一个新的01串,使得得到的新的01串中的一个子串最长(子串不一定连续),且这个子串是01间隔的,没......
  • CF1824B1 LuoTianyi and the Floating Islands (Easy Version) 题解
    题意:思路:由于$k∈[1,3]$,分类讨论:当$k=1$时,有人结点自身即为好结点,每种情况的期望为$\frac{1}{n}$,$n$种情况的期望和为$1$。最终答案即为$1$。当$k=2$时,$2$个有人结点之间的路径上的结点即为好结点,那么问题转化为:树上所有路径的结点......
  • ABC325G offence 题解
    给出一个长为\(n\)的字符串和非负整数\(k\)。你可以进行以下操作若干次,使得最终字符串长度最小。选择一个字串of。然后删掉of以及这之后的\(i\)个字符。\(i\)由你决定,但要满足\(0\leqi\leqk\)。输出这个最小长度。\(1\leqn,k\leq300\)。做完以后感觉很简单。但......
  • CTFpwn格式化字符串两种应用及2023ISCTF的fmt题解wp
    三个例子的引入目前我遇到的格式化字符串漏洞(formatstring,后文简称fmt)主要存在于printf函数,本文也就以printf举例。例一,标准格式的printf read(0,buf,33);printf("%s",buf);例二,占位符与变量 printf("%d%c%s",a,b,c);//%d%c%s会访问变量以输出整型,字符等。其中a,b,c为三......
  • [AGC032D] Rotation Sort 题解
    题目链接点击打开链接题目解法题目中的操作可以理解为一个点移动位置首先给出一个结论:每个点只会动至多一次考虑\(dp\)一个比较妙的状态设定是\(f_i\)表示\(i\)不动的方案数不妨枚举\(j\)表示上一个不动点,限制是\(j<i\)且\(p_j<p_i\)中间满足\(j<k<i\)且\(p_......
  • [AGC037D] Sorting a Grid 题解
    题目链接点击打开链接题目解法从后往前推一下,可以得到\(C\)一定要把每一行的数都归位到那一行,\(B\)一定要每一列的目标行数互不相同考虑构造\(B\)这个限制看起来略有些网络流,所以考虑如何建图令\(a_{i,j}\)的目标行数为\(ln_{i,j}\),我们由\(i\toln_{i,j}\)连边不......
  • [ABC254E] Small d and k 题解
    题目传送门一道暴力题。度数和\(k\)那么小?直接暴力\(n\)遍bfs,注意bfs的队列只能push距离不超过\(3\)的点。但有个问题,每次bfs都需要清空一次距离数组,这样子的时间复杂度是\(O(n^2)\)的。但也不难想到,距离数组中被赋值的地方不会很多,记录一下就行。Code#include......
  • RestTemplate 请求 webservice 中文乱码问题解决【问题解决】
    添加一个Converter设置UTF-8编码@ConfigurationpublicclassRestTemplateConfig{@BeanpublicRestTemplaterestTemplate(){RestTemplaterestTemplate=newRestTemplate();//添加自定义的ClientHttpRequestInterceptor全局JSON請......
  • [ARC141D] Non-divisible Set 题解
    题目链接点击打开链接题目解法很思维的题,需要用好所有的特殊性质暴力的做法是建出图,然后求包含点\(i\)的最长反链,但这明显过不了上面的做法没用到\(a_i<2m\)的性质如何用?把\(a_i\)拆分成\(q\times2^k\;(k\)为奇数\()\)的形式,那么对于同一个\(q\),只能在其中选一个......
  • [ARC141E] Sliding Edge on Torus 题解
    题目链接点击打开链接题目解法比较套路的题首先画个图,然后把\(y-x\)相同的变成一个点(使\(y>x\))然后再两个点之间连有权边那么问题就变成求新图的每个连通块中形成的原图的连通块数量手玩几个数据发现,原图的连通块数量即为新图的所有环长的\(\gcd\),再和\(n\)的\(\gcd......