NCPC 2014 Amanda Lounges 二分图染色

给一个图,有些边需要两端均为1,有些边两端均为0,有些边两端需要只有一个为1,问能不能实现,最少填多少个1.

对于两端都是1,和两端都是0的,我们暴力填上去,并且把相连的其他两端不同的顺上去。现在我们剩一些联通分量,边均为两端要求不同。我们对于每个联通分量任取一点,先后尝试填0,1,取最小值即[……]

Read more

OI康复训练 luogu 1983 车站分级 拓扑排序

这种水题先后读错n次题意,还链前没开好炸了内存,没想到邻接矩阵,QwQ。

Noi模拟 弹球游戏 费用流

弹球游戏(bounce)

【题目描述】

妹老师引进了一个新的弹球游戏,游戏区域是一个n*m的网格,格子坐标编号从(1,1)到(n,m),每个格子里都有一个斜面,斜面有四种摆放方式:

//此处自行YY四个正方形,分别被黑白分成两半,一半是一个等腰三角。

 

灰色[……]

Read more

bzoj 1443: [JSOI2009]游戏Game 二分图匹配

我们先明确一个事实,棋盘上alice和bob能走到的点必定是不同的,可以染成黑白相间网格,这样子我们从二分图匹配的角度考虑。

四联通建图,然后我们二分图匹配,然后我们可以发现如果可以得到完美匹配,则bob是必胜的。因为bob走一个匹配边,alice走一个非匹配边。只要还有非匹配边可以走,就必然[……]

Read more

bzoj 4443: [Scoi2015]小凸玩矩阵 二分+二分图匹配

题解:

求第k大,我们转化成求第n-k + 1小。然后我们二分一个值。对于原始矩阵如果mp[i][j]  <= x,那么我们就在行列的二分图里把i行和j列连上。然后跑一边二分图匹配,如果不小于n-k+1,那么认为结果可以更小。

我开始一直不太确定算法正确性,你能满足n-k+1个小的[……]

Read more

bzoj 2753: [SCOI2012]滑雪与时间胶囊 kruskal

看复杂度就不是最小树形图。显然是MST魔改以下。这个图相当于很大一部分是有向边,有一些小部分是无向边。按照从上(1号点高度)向下的顺序来,自然也就保证了正确性,保证了每次是从1号点的联通快连出去,用MST处理就行了,

以下为正解;

第一个问宽搜解决。

第二个问,按照第一关键字有向边[……]

Read more

bzoj 3158: 千钧一发 最小割

看到这道题 是没什么思路的。查了一句话题解说是最小割。让我想到了魔术球那题。想找二分图的性质,然而失败了。真是可惜。后来查了题解恍然大悟。

两个偶数显然满足gcd>1的条件。

两个奇数 (2a+1)^2 + (2b+1)^2 = 4a^2 + 4a + ab^2 + 4b + 2[……]

Read more

bzoj 3894: 文理分科 最大流

我们先不考虑一个人周围人选什么。建图就非常显然了。s连向所有人,流量为选文的满意度,所有人向t连边,流量为选理的满意度。然后我们考虑一下如果表示说自己和周围一圈四个人选择一样的科目带来的额外满意度呢。我们考虑新建两组点,分别表示一个人和周围四个人选文/理给这个人带来的额外满意度。我们从s连边到一个点[……]

Read more

bzoj 3732: Network 倍增lca kruscal

倍增lca里面注意返回值前上爬的最后一步,不要忘了。还有不要把数组名写混了。

在最小生成树上跑倍增lca即可。

bzoj 2132: 圈地计划 网络流

一眼就看出了是网络流,感觉xjb搞一搞很可做。然后xjb搞了半天弃疗了。

我们考虑,如果这道题变成相邻的相同有c的收益就简单了。建一个s,连向所有点,流量为a,所有点连向t,流量为b。相邻的点之间连双向流量为c的边,然后就好了。因为当x,y两个点相邻的点属于同侧时,相邻的点的双向流量不用被割。[……]

Read more