链接标题
复习最小路径覆盖
最小路径覆盖是指对于给定的DAG，用最少的路径将其所有点覆盖，路径不相交。最小路径覆盖建图如下：
变式1：最小链覆盖
用最少的路径将其所有点覆盖，路径可以相交
做法：使用floyd传递闭包重连边，然后进行最小路径覆盖
变式2：最长反链
指选择最多的点，使得两两之间不能互相到达
做法：对偶问题：最长反链等于最小链覆盖
本题中发现球是依次加入的，如果有两个球和为完全平方数那么小的向大的连接单向边，一个柱子就相当于一条路径。那么可以知道K" role="presentation" style="position: relative;"&
题目描述滑雪场坐落在FJ省西北部的若干座山上。 从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。 你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。 由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。 输入输出格式输入格式： 输入文件的第一行包含一个整数n (2 <= n <= 100) – 代表滑雪场的地点的数量。 接下来的n行，描述1
很套路的一道题，做过无限之环来看这道题还是十分好想的因为我比较菜，考试的时候就没能想出来。按照套路，把格子黑白染色，然后考虑图的特点，到一个地方一定拐弯。并且，对于一条回路来说，正向和反向的贡献都是一样的。接下来，我们指定黑、白格子的流向，考虑一个白格子的流出一定是某个黑格子的流入。那么就好办了，我们规定黑格子横进竖出，白格子横出竖进。这样我们把问题抽象成一张图，对于每一个格子可以选择从进向自己连边，自己向出连边，相当于每种进的方案都可以选择两种出去的方案。但是题目还有一个隐含条件，一个点只能经过一条流量，也就是出入度都是1，想到限制出入度便想到了最小路劲覆盖的模型。于是，初步的构图便完成了。
【题目描述】同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。 【输入】第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。 【输出】最小平均等待时间，答案精确到小数点后2位。 【输入样例】2 2
3 2
1 4 【输出样例】1.50 【提示】数据范围: (2<
题意翻译描述 掷骰子是一种双人游戏，它的结果是完全随机的。最近它在整个Byteotia变得非常流行。在Byteotia的首都甚至有一个特别的掷骰子业余爱好者俱乐部。俱乐部的老主顾们花时间互相聊天并每隔一阵子就和一个随机选择的对手玩这他们最喜欢的游戏。一天中赢得最多游戏的人会得到“幸运者”头衔。有时晚上俱乐部很安静，只有很少的比赛。这是哪怕赢一场也能获得“幸运者”头衔的时间。 很久很久以前有一个很不走运的人，叫Byteasar，赢得了这个光荣的头衔。他被深深地震惊了以至于完全忘了他已经赢了多少场。现在他想知道他有多幸运，以及幸运之神是否最终会向他微笑——也许他的运气会变好？他确切地知道在那个幸运
题目描述申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。 输入输出格式输入格式： 第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种
题目描述给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大 输入输出格式输入格式： 第一行两个数n,k（1<=n<=50, 0<=k<=10） 接下来n行,每行n个数,分别表示矩阵的每个格子的数 输出格式： 一个数,为最大和 输入输出样例输入样例#1： 复制3 1
1 2 3
0
题目描述火星探险队的登陆舱将在火星表面着陆，登陆舱内有多部障碍物探测车。登陆舱着陆后，探测车将离开登陆舱向先期到达的传送器方向移动。探测车在移动中还必须采集岩石标本。每一块岩石标本由最先遇到它的探测车完成采集。每块岩石标本只能被采集一次。岩石标本被采集后，其他探测车可以从原来岩石标本所在处通过。探测车不能通过有障碍的地面。本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动，而且多个探测车可以在同一时间占据同一位置。如果某个探测车在到达传送器以前不能继续前进，则该车所采集的岩石标本将全部损失。 用一个 P·Q 网格表示登陆舱与传送器之间的位置。登陆舱的位置在(X1,Y1)处，传送器 的位
题目描述如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。 输入输出格式输入格式： 第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。 接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi） 输出格式： 一行，包含一个正整数，即为该网络的最大流。 输入输出样例输入样例#1： 复制4 5 4 3
4 2 30
4 3 20
2 3 2
题目描述农夫约翰的奶牛们喜欢通过电邮保持联系，于是她们建立了一个奶牛电脑网络，以便互相交流。这些机器用如下的方式发送电邮：如果存在一个由c台电脑组成的序列a1,a2,...,a(c)，且a1与a2相连，a2与a3相连，等等，那么电脑a1和a(c)就可以互发电邮。 很不幸，有时候奶牛会不小心踩到电脑上，农夫约翰的车也可能碾过电脑，这台倒霉的电脑就会坏掉。这意味着这台电脑不能再发送电邮了，于是与这台电脑相关的连接也就不可用了。 有两头奶牛就想：如果我们两个不能互发电邮，至少需要坏掉多少台电脑呢？请编写一个程序为她们计算这个最小值。 以如下网络为例： 1* / 3 - 2* 这张图画的是有2条连接的
Rockdu's Blog