奥运公交[LOJ3255]

题目描述JOI 王国共有$N$个城市,这些城市从$1$到$N$编号。共有$M$条公交线路连接这些城市,这些线路从$1$到$M$编号。第$i$条公交线是从城市$U_i$到城市$V_i$的,票价为$C_i$日元。如果乘客乘坐第$i$条公交线,他只能在城市$U_i$上车,在城市$V_i$下车。从一个城市到另一个城市可能有多条公交线。 不久,JOI 王国将举办奥运会。K 理事长是 JOI 王国交通部...

遗产「CF 787D」

【题目描述】Rick和他的同事制作了一种新的放射性配方,很多坏人都跟着他们。所以Rick想要在坏人抓住他们之前将他的遗产交给Morty。他们的宇宙中有$n$个行星从$1$到$n$编号。Rick在行星编号$s$(地球),他不知道Morty在哪里。众所周知,里克拥有一支门卫枪。有了这把枪,他就可以打开从他所在行星到任何其他星球(包括那个星球)的单向门。但这支枪有一些限制,因为他仍在使用免费试用版...

Small Multiple[ARC084 B]

【题目描述】给定一个整数$k$.求一个$k$的整数倍$sum$,使得$sum$的数字和最小 题解 考试的时候想尽一切办法枚举,卡时 最多卡到70pts 其实如果把那几个最毒瘤的数放上去完全可以把暴力卡掉 正解是要建图跑最短路 考虑$sum$在模$k$意义下的值 我们建立$k$个节点 编号为$0\sim n-1$ 对于每个$i$连一条$i$到$(i+1)\operatorname{mod}...

小Biu看电影

【题目描述】无聊的小Biu来到了电影之城,他发现这里有$n$个电影院,而且每个电影院的电影票价是不同的,有一些电影院之间有双向联通的道路,想要通过某条道路需要一定的花费,小Biu想知道,他以每一个电影院为起点(当然也可以原地不动),最少需要多少花费可以看到电影。 【输入格式】第 1 行:两个整数$n,m$,$n$表示城市中电影院的个数,$m$表示电影院之间的道路总数。($1\leq n\le...

贫富差距

【题目描述】一个国家有$N$个公民,标记为$0,1,2,…,N-1$,每个公民有一个存款额。已知每个公民有一些朋友,同时国家有一条规定朋友间的存款额之差不能大于$d$。也就是说,$a$和$b$是朋友的话,$a$有$x$元的存款,$b$有$y$元,那么$|x-y|\leq d$。给定$d$值与$N$个人的朋友关系,求这个国家最富有的人和最贫穷的人的存款相差最大的可能值是多少?即求贫富差距的最大...

糖果「SCOI2011」

【题目描述】幼儿园里有$N$个小朋友,$lxhgww$老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候,$lxhgww$需要满足小朋友们的$K$个要求。幼儿园的糖果总是有限的,$lxhgww$想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所...

物流运输trans「ZJOI2006」

【题目描述】物流公司要把一批货物从码头$A$运到码头$B$。由于货物量比较大,需要$n$天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情,会带来额外的成本。因此物流公司希望能够订一...

大陆争霸[SDOI2010]

只要你有无限个自爆机器人,你就能为所欲为 斯普林·布拉泽 【题目描述】略一句话题意:杰森国有$N$个城市,由$M$条单向道 路连接。杰森国的首都是城市$N$。你只需摧毁杰森国首都就能获胜。为了尽量减小己方的消耗,你决定使用自爆机器人完成这一任务。唯一的困难是,杰森国的一部分城市有结界保护,不破坏掉结界就无法进入城市。而每个城市的结界都是由分布在其他城市中的一些结界发生器维持的,...

逛公园「NOIP2017」

大家好我叫蒟蒻,这是我的第一篇信竞题解blog 【题目描述】策策同学特别喜欢逛公园。 公园可以看成一张$N$个点$M$条边构成的有向图,且没有自环和重边。其中$1$号点是公园的入口,$N$号点是公园的出口,每条边有一个非负权值,代表策策经过这条边所要花的时间。 策策每天都会去逛公园,他总是从$1$号点进去,从$N$号点出来。 策策喜欢新鲜的事物,他不希望有两天逛公园的路线完全一样,同时策策...