很套路的一道题，做过无限之环来看这道题还是十分好想的因为我比较菜，考试的时候就没能想出来。按照套路，把格子黑白染色，然后考虑图的特点，到一个地方一定拐弯。并且，对于一条回路来说，正向和反向的贡献都是一样的。接下来，我们指定黑、白格子的流向，考虑一个白格子的流出一定是某个黑格子的流入。那么就好办了，我们规定黑格子横进竖出，白格子横出竖进。这样我们把问题抽象成一张图，对于每一个格子可以选择从进向自己连边，自己向出连边，相当于每种进的方案都可以选择两种出去的方案。但是题目还有一个隐含条件，一个点只能经过一条流量，也就是出入度都是1，想到限制出入度便想到了最小路劲覆盖的模型。于是，初步的构图便完成了。
【题目描述】同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。 【输入】第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。 【输出】最小平均等待时间，答案精确到小数点后2位。 【输入样例】2 2
3 2
1 4 【输出样例】1.50 【提示】数据范围: (2<
题目描述申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要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)处，传送器 的位
Rockdu's Blog