最小割 - hzwer.com

2017ACM萧山训练第5场(2016 Pacific Northwest – Division 1)
E.Enclosure做出大小两个凸包，即所有点的凸包和前k个点的凸包按动态凸包的思路，新加入的点会把小凸包上连续的一些点弹出，这些点是一个连续的区间相当于切掉凸包的一个角，加入一个三角形若在大凸包上顺时针枚举一个加入的点，这个区间左右端点也是顺时针转的，类似旋转卡壳切掉部分的面积顺便维护由于坐标范围较大，用double精度会炸[crayon-673fbd536b0f7978337009/]G.MaximumIslandsL的上下左右直接贪心为W然后剩下的就...
02017年8月11日6,502贪心,ST表,最小割,凸包,二分法,旋转卡壳

Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)
A.CheckingtheCalendar问有没有可能存在一年中的连续两个月，第一个月的第一天的星期是给定的第一个字符串，第二个月的第一天的星期是给定的第二个字符串模拟即可[crayon-673fbd536c2df039681463/]B.BatchSort给你n行，每行都是一个1-m的排列。\(1\leqn\leq20,1\leqm\leq20\)你可以交换任意两列，并且你可以每行最多交换两个元素，问你能不能使得每行都是单增的枚举两列交换，每行贪心[crayon-673fbd536c2e8023101183/]C.R...
02016年11月10日5,305模拟,递推与动规,贪心,最小割
2016 ACM / ICPC Asia Regional Qingdao Online
大部分都是队友写的代码QAQ我主要是填坑个题解1001ICountTwoThree定义『ICountTwoThreeNumber』为\(2^a3^b5^c7^d\)问超过n的最小的这种数字显然这样的数字数量是很少的，其质因数个数不会超过30个dfs出所有数字，二分查询1002Cure求\(\sum\limits_{k=1}^n\frac{1}{k^2}\)\(\lim_{n\rightarrow\infty}\)\(\sum\limits_{k=1}^n\frac{1}{k^2}=\frac{\pi^2}{6}\)n超过十几万之后就达到精度上限1003FamilyView把一个文本...
12016年10月8日7,723哈夫曼树,最小割,STL,dijkstra,深度搜索,二分法,欧拉图,AC自动机,记忆化搜索
POJ训练记录
1966.CableTVNetwork枚举源汇求最小割[crayon-673fbd536cfcd371615113/]2386.LakeCounting搜索[crayon-673fbd536cfd9748306538/]3863.BusinessCenter枚举每个电梯，二分求最小值[crayon-673fbd536cfe0046041337/]2504.Boundingbox求外心然后旋转n次得到多边形坐标精度弃坑。。[crayon-673fbd536cfe4428052641/]3155.HardLife最大密度子图+方案分数规划[crayon-673fbd536cfea175451540/]4028.GCDGuessingGame贪心策...
02015年5月13日4,770贪心,最小割,深度搜索,二分法,几何
「BZOJ3996」[TJOI2015] 线性代数
Description给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得D=（A*B-C）*A^T最大。其中A^T为A的转置。输出DInput第一行输入一个整数N，接下来N行输入B矩阵，第i行第J个数字代表Bij.接下来一行输入N个整数，代表矩阵C。矩阵B和矩阵C中每个数字都是不超过1000的非负整数。Output输出最大的DSampleInput3121310123237SampleOutput2HINT 1<=N<=500题解倒腾下式子发现是...
02015年4月22日5,979最小割
「BZOJ1797」[Ahoi2009] Mincut 最小割
DescriptionA,B两个国家正在交战，其中A国的物资运输网中有N个中转站，M条单向道路。设其中第i(1≤i≤M)条道路连接了vi,ui两个中转站，那么中转站vi可以通过该道路到达ui中转站，如果切断这条道路，需要代价ci。现在B国想找出一个路径切断方案，使中转站s不能到达中转站t，并且切断路径的代价之和最小。小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题：问题一...
62015年4月7日10,399最小割,图的连通
「East!_XVI」九尾妖狐
Background某无良设计师伊泽瑞尔:刀妹太弱了,我们来增强阿狸吧。Description阿狸现在有N个技能,伊泽瑞尔要决定它们是AD技能还是AP技能。因为出装不同,所以当一个技能是AP时,阿狸的爆发增加ap_i,当一个技能是AD时,阿狸的爆发增加ad_i。有些技能配合可以打出伤害加成,这样阿狸的技能就可以被表示为一张无向图。当有关联的两个技能都是AD时,阿狸的爆发增加AD_i,当两个技能都是AP时,阿狸的爆发增加AP_i,当两个技能不...
02015年4月4日4,383最小割
「BZOJ3894」文理分科
Description 文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠结过）小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到：1．如果第i行第秒J的同学选择了文科，则他将获得art[i][j]的满意值，如果选择理科，将得到science[i][j]的满意值。2．如果第i行...
22015年3月25日7,691最小割
「BZOJ3144」[HNOI2013] 切糕
DescriptionInput第一行是三个正整数P,Q,R，表示切糕的长P、宽Q、高R。第二行有一个非负整数D，表示光滑性要求。接下来是R个P行Q列的矩阵，第z个矩阵的第x行第y列是v(x,y,z)(1≤x≤P,1≤y≤Q,1≤z≤R)。100%的数据满足P,Q,R≤40，0≤D≤R，且给出的所有的不和谐值不超过1000。Output仅包含一个整数，表示在合法基础上最小的总不和谐值。SampleInput222161612626SampleOutput6HINT最佳切面的f为f(1,1)...
12015年2月5日6,726最小割
「BZOJ2229」[ZJOI2011] 最小割
Description小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话：“对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点s,t不在同一个部分中，则称这个划分是关于s,t的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而s,t的最小割指的是在关于s,t的割中容量最小的割”现给定一张无向图，小白有若干个形如“图中有多少对点它们的最...
72015年1月28日8,797最小割
「BZOJ2400」SPOJ 839 Optimal Marks
Description定义无向图中的一条边的值为：这条边连接的两个点的值的异或值。定义一个无向图的值为：这个无向图所有边的值的和。给你一个有n个结点m条边的无向图。其中的一些点的值是给定的，而其余的点的值由你决定（但要求均为非负数），使得这个无向图的值最小。在无向图的值最小的前提下，使得无向图中所有点的值的和最小。Input第一行，两个数n，m，表示图的点数和边数。接下来n行，每行一个数，按编号给出每个点的值（若为负...
22014年12月27日5,706最小割
「泉七培训 – 杨国烨」图
「题目描述」给一张联通无向图，定义Dist[i][j]表示点i到点j之间的最短路。当前已经有了若干条的边，再给定N个A[i]，要求添加若干条无向边，使得Σ(a[i]-Dist[1][i])^2最小。输出最小的答案。「输入格式」第一行是整数N，表示节点数。接下来是N*N的矩阵，mat[i][j]=‘Y’表示i和j之间有一条无向边。保证mat[i][j]=mat[j][i]。接下来N个数，表示A[i]。「输出格式」求答案。「样例输入」4NYNNYNYNNYNYNNYN...
02014年12月26日4,249最小割