二分图匹配 - hzwer.com

2017ACM萧山训练第2场(NWERC 2008)
A:EquilibriumMobile最终天平平衡的状态下，每个结点x满足w[x]*(2^dep[x])相等统计所有的w[x]*(2^dep[x])，答案是叶子数减去出现次数最多的个数[crayon-6767b1afe5bc8640063747/]B:ProvingEquivalences答案是max{入度为0的连通块个数，出度为0的连通块个数}特判连通块为1的情况每个连通块，出度0的点，向其它入度为0的连边，使得形成一个环[crayon-6767b1afe5bd8115595622/]C:Catvs.Dog找出所有相互不兼容的人，将他们连边...
12017年8月8日6,114递推与动规,贪心,单调队列,图的连通,二分图匹配,扩展欧几里得算法

「BZOJ4205」「FJ2015集训」卡牌配对
卡牌配对「问题描述」现在有一种卡牌游戏，每张卡牌上有三个属性值：A,B,C。把卡牌分为X,Y两类，分别有n1,n2张。两张卡牌能够配对，当且仅当，存在至多一项属性值使得两张卡牌该项属性值互质，且两张卡牌类别不同。比如一张X类卡牌属性值分别是225,233,101，一张Y类卡牌属性值分别为115,466,99。那么这两张牌是可以配对的，因为只有101和99一组属性互质。游戏的目的是最大化匹配上的卡牌组数，当然每张卡牌只能用一次。「输...
32015年7月5日5,656二分图匹配,网络流
NOI2009变换序列
DescriptionInputOutputSampleInput511221SampleOutput12403HINT30%的数据中N≤50；60%的数据中N≤500；100%的数据中N≤10000。题解byvoid大神：https://www.byvoid.com/blog/noi-2009-transform/[crayon-6767b1afe786f847341239/]...
02015年6月29日3,939二分图匹配
TCO 2015 Round 1A DIV1
250：枚举l-r的数，爆搜，统计数位，用map存一下TT实际上对于每个数小范围暴力即可TT[crayon-6767b1afe7c3f503699373/]500：暴力走min(n^2,K)次，预处理出哪些不能同时取。。。再暴搜+快速幂算方案TAT结果有个点T了。。。正解假如k步之前在一起了，那么k步的时候一定在一起了所以如果我们能求出k步的状态，就可以用每个数出现的次数+1的乘积作为答案（可以选择任意数量的放，也可以不放）所以暴力求状态后乘起来就行了。。...
02015年4月15日34,036STL,深度搜索,二分图匹配
「CODEVS1222」信与信封问题
题目描述 DescriptionJohn先生晚上写了n封信，并相应地写了n个信封将信装好，准备寄出。但是，第二天John的儿子Small John将这n封信都拿出了信封。不幸的是，Small John无法将拿出的信正确地装回信封中了。将Small John所提供的n封信依次编号为1，2，…，n；且n个信封也依次编号为1，2，…，n。假定Small John能提供一组信息：第i封信肯定不是装在信封j中。请编程帮助Small John，尽可能多地将信正确地装...
02014年3月2日4,886二分图匹配
「BZOJ1059」[ZJOI2007] 矩阵游戏
Description小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）列交换操作：选择矩阵的任意行列，交换这两列（即交换对应格子的颜色）游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的...
02014年1月7日6,360二分图匹配
「BZOJ1191」[HNOI2006] 超级英雄Hero
Description现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”，比如求助现场观众，或者去掉若干个错误答案（选择题）等等。这里，我们把规则稍微改变一下。假设主持人总共...
02014年1月6日5,333二分图匹配
「vijos1212」Way Selection
背景小杉家族遭遇了前所未有的大危机他想知道怎么逃生描述小杉家族r个人正在一片空地上散步，突然，外星人来了……留给小杉家族脱逃的时间只有t秒，每个小杉都有一个跑的速度v总共有a个传送点，小杉们必须在t秒内到达传送点才能脱逃另外一个小杉进入一个传送点以后，该传送点就会消失现在请你安排一种方案，使脱逃的小杉尽可能的多输入格式每组测试数据的第一行有三个整数r和a和t(0<a,r,t<=1000)第二行有a对实数，第i对数表示...
02013年12月19日2,905二分图匹配
「RQNOJ191」梦幻大PK
题目描述难得到了生日，正逢上班里面一年一度的梦幻大PK，分2组对拼。但是由于某种原因，参加PK的第1组中有些人不能和第2组人PK。可能是因为等级、互克、相生等关系。于是，南瓜（为鄙班中队长and团支书）想要确定最多要多少次PK。十分惋惜，因为鄙人的大名在学校大黑板上挂了2个月（就是全国1=而已拉）了。于是就来found鄙人。但是鄙人正准备着自己的生日，于是只好把这个难题交付各位OIers了。十分遗憾，南瓜小姐的统计...
12013年11月26日3,022二分图匹配
「RQNOJ140」寻找代表元
题目描述温中一共有n个社团，分别用1到n编号。温中一共有m个人，分别用1到m编号。每个人可以参加一个或多个社团，也可以不参加任何社团。每个社团都需要选一个代表。我们希望更多的人能够成为代表。输入格式第一行输入两个数n和m。以下n行每行若干个数，这些数都是不超过m的正整数。其中第i行的数表示社团i的全部成员。每行用一个0结束。数据范围：n,m<=200 输出格式输出最多的能够成为代表的人数。样例输入44...
02013年11月25日3,394二分图匹配