Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

12/7
16:08
最小割

[bzoj 1585] [Usaco2009 Mar]Earthquake Damage 2 地震伤害

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

Farmer John的农场里有P个牧场,有C条无向道路连接着他们,第i条道路连接着两个牧场Ai和Bi,注意可能有很多条道路连接着相同的Ai和Bi,并且Ai有可能和Bi相等。Farmer John在1号牧场里。由于地震,某些牧场被损坏,但由于信春哥,C条道路没有一条损坏。有N头奶牛,他们在不同的牧场里,于是N <= P。他们一一向Farmer John报告。第i头奶牛报告给Farmer John一个整数Report_i,代表第Report_i个牧场没有损毁,但不能够从第Report_i个牧场经过一些没有损坏的牧场到达1号牧场。现在Farmer John想知道,最少有多少损坏的牧场。

Read More →

[bzoj 1585] [Usaco2009 Mar]Earthquake Damage 2 地震伤害

@krydom1年前

12/6
20:39
dijkstra 最小割

[bzoj 1266] [AHOI2006]上学路线route

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

可可和卡卡家住合肥市的东郊,每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。 可可:“很可能我们在上学的路途上浪费了大量的时间,让我们写一个程序来计算上学需要的最少时间吧!” 合肥市一共设有N个公交车站,不妨将它们编号为1…N的自然数,并认为可可和卡卡家住在1号汽车站附近,而他们学校在N号汽车站。市内有M条直达汽车路线,执行第i条路线的公交车往返于站点pi和qi之间,从起点到终点需要花费的时间为ti。(1<=i<=M, 1<=pi, qi<=N) 两个人坐在电脑前,根据上面的信息很快就编程算出了最优的乘车方案。然而可可忽然有了一个鬼点子,他想趁卡卡不备,在卡卡的输入数据中删去一些路线,从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线i事实上都有一个代价ci:删去路线的ci越大卡卡就越容易发现这个玩笑,可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线ci之和最小。 [任务] 编写一个程序:  从输入文件中读取合肥市公交路线的信息;  计算出实际上可可和卡卡上学需要花费的最少时间;  帮助可可设计一个方案,删除输入信息中的一些公交路线,使得删除后从家到学校需要的最少时间变大,而被删除路线的ci和最小;向输出文件输出答案。

Read More →

[bzoj 1266] [AHOI2006]上学路线route

@krydom1年前

10/15
10:24
最小割

[bzoj 3275] Number

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 有N个正整数,需要从中选出一些数,使这些数的和最大。
若两个数a,b同时满足以下条件,则a,b不能同时被选
1:存在正整数C,使a*a+b*b=c*c
2:gcd(a,b)=1

Read More →

[bzoj 3275] Number

@krydom1年前

09/24
16:44
最小割

[bzoj 3894] 文理分科

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

文理分科是一件很纠结的事情!(虽然看到这个题目的人肯定都没有纠结过)
 小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行描述,每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到:
1.如果第i行第秒J的同学选择了文科,则他将获得art[i][j]的满意值,如果选择理科,将得到science[i][j]的满意值。
2.如果第i行第J列的同学选择了文科,并且他相邻(两个格子相邻当且仅当它们拥有一条相同的边)的同学全部选择了文科,则他会更开心,所以会增加same_art[i][j]的满意值。
3.如果第i行第j列的同学选择了理科,并且他相邻的同学全部选择了理科,则增加same_science[i]j[]的满意值。
小P想知道,大家应该如何选择,才能使所有人的满意值之和最大。请告诉他这个最大值。

Read More →

[bzoj 3894] 文理分科

@krydom1年前

09/11
13:38
最小割

[bzoj 4485] [Jsoi2015]圈地

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 【故事背景】
JYY在火星买了一大块矩形的地皮做房地产开发。由于地皮实在是太大了,JYY把这块地皮划分成了N行M列的小方格,并在每一格中建造一栋房子。历时若干年,开发终于宣告结束,JYY也可以把这些房子挂牌出售了。现在他找到了两位非同寻常的土豪买家:南南和强强。
麻烦的是,南南和强强是水火不容的。为了保证他们俩不发生矛盾,JYY需要把卖给他们俩的房子用墙隔开。不过造墙是需要钱的,JYY作为倒卖地皮的专家,自然想挣尽可能多的钱,因此他邀请到你帮他设计最优的出售方案。
【问题描述】
JYY把这块地皮划分成了N行M列的矩形,且矩形的每一格中建造一栋房子。现在,南南和强强已经将他们的购买意见提交给了JYY。对于每一栋房子,南南和强强已经给定了他们的出价(不想购买,或愿意以一定价格购买),并且由于他们已经协商好了各自的势力范围,因此不存在两个人同时想买一栋房子的情况。JYY可以选择每一栋房子是否出售(因为不存在两个人同时想买一栋房子的情况,若JYY选择出售一栋房子,它的买家就是确定的)。房子卖给强强和南南以后,JYY就能获得卖出房子出价的总和。
不过,作为售后服务,JYY需要通过造墙(将两栋相邻的房子用一堵墙隔开)把两个人的房子完全隔开。所谓完全隔开,就是指造出的墙以及四周的边界将整个区域划分成若干个不连通的部分,每个部分里面只有一个人的房子。当然,造墙也是需要钱的,而且价格不菲。不过JYY当初在宣传时声称造墙完全免费,所以这部分钱只好由JYY自己出了。
JYY请你为他规划每幢房子是否要卖出以及建造哪些围墙,才能使得卖房子的收益减去造围墙的花费最大。另外一个好消息是整个地皮的四周已经建好了墙,因此JYY可以利用这些建好的墙达到目的。下图就是用墙将区域划分成3个不连通的部分的例子。格子中的数字代表出价(数字的含义参考输入格式),边上的数值代表造墙的价格。四周的墙(边界)本来就有,不需要JYY花额外的代价去建造。
4

Read More →

[bzoj 4485] [Jsoi2015]圈地

@krydom1年前

06/22
14:54
最小割

[bzoj 2127] happiness

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 高一一班的座位表是个n*m的矩阵,经过一个学期的相处,每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了,每个同学对于选择文科与理科有着自己的喜悦值,而一对好朋友如果能同时选文科或者理科,那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板,想知道如何分配可以使得全班的喜悦值总和最大。

Read More →

[bzoj 2127] happiness

@krydom1年前

06/15
16:52
最小割

[bzoj 1391] [Ceoi2008]order

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

有N个工作,M种机器,每种机器你可以租或者买过来. 每个工作包括若干道工序,每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。 现在给出这些参数,求最大利润

Read More →

[bzoj 1391] [Ceoi2008]order

@krydom1年前

06/14
14:20
最小割

[bzoj 2521] [Shoi2010]最小生成树

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 Secsa最近对最小生成树问题特别感兴趣。他已经知道如果要去求出一个n个点、m条边的无向图的最小生成树有一个Krustal算法和另一个Prim的算法。另外,他还知道,某一个图可能有多种不同的最小生成树。当然啦,这些都不是今天需要你解决的问题。Secsa想知道对于某一条无向图中的边AB,至少需要多少代价可以保证AB边在这个无向图的最小生成树中。为了使得AB边一定在最小生成树中,你可以对这个无向图进行操作,一次单独的操作是指:先选择一条图中的边 P1P2,再把图中除了这条边以外的边,每一条的权值都减少1

Read More →

[bzoj 2521] [Shoi2010]最小生成树