Beta Round #1 (新疆省队互测Week1-Day1)

OI - Official

From tangjz Kinger Tangent


小时

尚未报名

晒妹什么的都去死吧 9/46 From
为了信仰 5/33 From
Bread & Lemon 的期待 9/24 From

新疆省队互测 Week1 Day1

本次由tangjz出题,OI赛制,三道题目

难度不好说,神犇肯定无压力……

 

Kinger Tangent: 这场比赛无难度 求不被"原题"求不黑

tangjz: 祝各位AK各类比赛

 

flag:

第一题:请注意字典序是指边的编号。

第二题:感谢@hzhwcmhf提供的数据,数据已加强。

欢迎您在赛后提供更加强有力的数据,为保障选手利益,不会重新计算Rating。

 

简要题解:

第一题:求出最大流,最大流=最小割,字典序枚举满流边是否为割边即可。

第二题:50分算法是设黑代价为0白代价为1求单源最短路;100分算法是经典状压dp,按格dfs转移。

第三题:做法有很多,见bzoj1050

 

更新:

(2014.4.1)第二题数据更新,进行了加强;为防卡评测机,数据范围缩小。