over 1 year ago

hdu3840
题意:
有个nn(n<=40)的网格,要在里面放芯片
有些格能放,有些已放,有些让你选
给出a,b 使每行每列的芯片数不大于总数a/b 问总共最多放多少
题解:
好难啊被虐爆了
首先可以枚举每行列最多放多少个x,算出此时最多芯片数y,检验一下,合法就更新答案
枚举后,要限制行和列的相同 于是构造二分图,一边行,一边列
若某格(x,y)有芯片,则x行向y列有1流量 从i列向i行连一条边 做循环流就保证合法 因为i列被选后i行也要选一个列流出这个流量
然后要求总芯片最多,并且有些是一定要选的
就转化为最大费用循环流,一定要选就把他的费用设为很大

hdu3157
题意:
有源汇上下界最小流
题解:
超级源汇、连边都和上下界一样 平时上下界会在原汇到原源连一条下界0,上界inf的边 现在先不连做一次最大流 再连上做一次那条边流量就是答案
因为要最小化这条边的流量就先让能流别的地方先流别的地方,剩下就是非要流这条边的了

hdu4859
题意:
有个nm的格子(n,m<=47),有些地方是陆地有些是海有些让你选。若两个相邻格子不同,则他们之间有一条海岸线,nm外默认为海。选一个方案让总海岸线最长。
题解:
本来每条边都能成为海岸线 当相邻两个格选了相同的东西的时候就会有1的损失 因为是相同所以要二分图黑格正着建 白格反着建

hdu5594
题意:
有n(<=200)个数,问能否将他们分为若干个环,使每个环相邻两数相加为质数 环大小至少为3
题解:
好难啊被虐爆了
首先可以暴力看哪两个数可以相邻
如果忽略1的话相邻两数一定是1奇1偶
本来环的模型是1出度1入度
为了限制大小,做个二分图 让奇数连到偶数 源到奇数2容量,奇数到偶数1容量,偶数到汇2容量 这样若满流,就保证环至少为4
先将1当奇数补到奇偶数相同,若满流就有解 很多1可以当成1个1来用
有1种特殊情况就是1-x(如2)-1 这种情况只发生在所有1和x在一个环上 若不是的话可以拼上去 此时就如果要加入的1个数为1并且1总数大于1就把他到偶数的边连2
无解情况yy就好了

bzoj3144
题意:
有个abc的立方体(a,b,c<=40)要横向切开,要切开一个ab的面,要求面上相邻两点高度差不能大于d。每个点都有花费,问总花费最少
题解:
麻麻我会做切糕辣
我会告诉你我做过rin吗。。
考虑如何限制高度差

这样就能限制蓝色那条边了

uva11604
题意:
给n(<=100)个01串,每个长度不超过20 问有没有办法拼出两个相同的串 拼法不能完全相同 每个01串可在两个串中多次出现
题解:
好难啊被虐爆了
两个大串g1,g2
考虑每次都给g1加入一个串,g2跟着g1用合法串匹配,最后匹配了某一段前缀
首先可以枚举两两串做exkmp
假设s1[1..i]匹配s2[j..j+i-1]看看有什么用
1、i=len1 j+i-1=len2 如果g2走到了s2[j]那就能g1加s1,g2匹配完成 从s2[j]向终点连一条边
2、i=len1 j+i-1< len2 如果g2走到了s2[j],g1加入s1,g2走到j+i-1 从s2[j]向s2[j+i-1]连一条边
3、i< len1 j+i-1=len2 此时调换g1和g2 换后g1加入s1,g2走到s1[i+1] 从s2[j]向s1[i+1]连一条边
4、i< len1 j+i-1< len2 此时并没有什么卵用,因为考虑g1是完整的串拼成,最终答案一定可以是一直加完整的串
连完边后把每个串开头和起点相连,看看起点到终点连不连通就行了

la3661
题意:
给nm(n,m<=1000)的格子,格子间有这样的边


割一些边让起点和终点不连通,问最少花费
题解:
好难啊被虐爆了
最小割肯定可以,但太慢了
由于图的特殊性,割的边一定是这样的

就是从坐下到右上。
就把那些三角形的三条边当成点,互相连边 左边和下边连起点,右边和上边连终点 最短路就是答案

bzoj1312
题意:
麻烦程度可以认为是(带来麻烦的人的对数/总人数)。求最大麻烦程度时总人数最大。在这样的一个公司中,保证公司的人数小于100人,带来麻烦的员工不会多于1000对。
题解:
最大密度子图 边权/点权最大
二分k 表示 检验a/b>=k能否成立 即a-kb>=0是否成立
点权乘上k后 边权为正数 点权为负数 选一条边必选那两点
看最大权闭合子图是否大于0
大于0就找割边,就是我们尽量割连点权和汇的边 那就把必定不是割边连点权和汇的边(残量大于0)的拿出来 剩下的就是割边
此时合法且最大

← 2016-4-1 YZX ROUND poi练习记 →