给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大 输入格式 第一行两个数n,k（1<=n<=50, 0<=k<=10） 接下来n行,每行n个数,分别表示矩阵的每个格子的数 输出格式 一个数,为最大和 输入输出样例 输入 3 1 1 2 3 0 2 1 1 4 2 输出 11 相信做到这道题，大多数人应该做过k等于2的情况吧，当k等于2时，我们可以直接dp，令 d...

题目描述 在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。 输入格式 第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。 输出格式 程序运行结束时，将取数的最大总和输出 输入输出样例 输入 3 3 1 2 3 3 2 3 2 3 1 输出 11 看到题目，我们不难看出，可以把这个图，看成二分图。 然后我们就会想，怎么利用而二分图...

题目描述 众所周知，杨老师是一位十分勤奋的老师，他非常的热爱学习。 勤奋的他为自己罗列了一个学习清单，共有n个知识点，他可以有选择的进行学习。 每个知识点都会对应0个或1个或多个先修知识点（只有学会了先修知识点才能学习该知识点），同时每个知识点都有一个智慧值和一个智力消耗值。 杨老师希望在进行过激烈的学习之后，他的收获可以·量化为所有学过的题的智慧值的和与智力消耗值的和的差值。请问，这个值最大是多少？ 输入描述: 第一行：一个整数n（n<=500）接下来n行，每行两个整数，代表第i个知识点的智慧值和智力消耗值接下来若干行，每行2个整数u, v，代表u是v的先修知识点。 输出描...

题目描述 lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，然后只能使用某个属性值为2的装备攻击boss，然后只能使用某个属性值为3的装备攻击boss……以此类推。现在lxhgww想知道他最多能连续攻击boss多少次...

题目描述 W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1，E2，…，Em}，和进行这些实验需要使用的全部仪器的集合I={I1，I2，…In}。实验Ej需要用到的仪器是I的子集RjÍI。配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。 对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划...

题目描述 假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。 对于给定的组卷要求，计算满足要求的组卷方案。 输入格式 第1行有2个正整数k和n (2 <=k<= 20, k<=n<= 1000) k 表示题库中试题类型总数，n 表示题库中试题总数。第2 行有k 个正整数，第i 个正整数表示要选出的类型i的题数。这k个数相加就是要选出的总题数m。接下来的n行给出了题库中每个试题的类型信息。每行的第1 个正整数p表明该题可以属于p类，接着的p...

题目 求有向无环图的最小路径覆盖（可以从任意一个点开始） 题目链接：洛谷P 2764 二分图性质：最小路径覆盖 == 顶点数 - 最大匹配数 所以此题我们可以转化为求最大匹配来做，但是麻烦的是输出路径。 考虑建图： 我们可以把点拆成两个点，分别为入点和出点，让超级源点S连向每个点的入点，让每个点的出点连向超级汇点T，然后如果u能到达v，那么就让u的入点连向v的出点即可。（建图完成） 然后跑一遍最大流，答案就是总的点数 n - dinic() 考虑输出路径： 我们输出路径，主要就是要找到每个边集合开始的边，很多人都用并查集来维护边的关系，但是我觉得完全没有必要，我们...

定义：通俗点讲，就是在一个有向图中，找出最少的路径，使得这些路径经过了所有的点。 而最小路径覆盖又分为：最小不相交路径覆盖 和 最小可相交路径覆盖。 最小不相交路径覆盖 ： 就是我们找到的每条路径不能相交，就是每条路径不能有同一个点。 最小可相交路径覆盖 ： 这个与上面相对应，就是可以相交。 注意：每个点被自己覆盖，路径长度为0 求解最小不相交路径覆盖： 我们把每个点都拆成两个点，分为入点和出点，如果 u 到 v 有边，那么我们就让 u 的入点连向 v 的出点 ， 最后跑一下最大流或者匈牙利 算出最大匹配。答案就是 点的数目 - 最大匹配数 求解最小可相交路径覆盖： 和上面很相似...

这篇博客是个极其简单的东西。 如题，给出一个N次函数，保证在范围[l,r]内存在一点x，使得[l,x]上单调增，[x,r]上单调减。试求出x的值。 输入格式 第一行一次包含一个正整数N和两个实数l、r，含义如题目描述所示。 第二行包含N+1个实数，从高到低依次表示该N次函数各项的系数。 输出格式 输出为一行，包含一个实数，即为x的值。四舍五入保留5位小数。 输入 3 -0.9981 0.5 1 -3 -3 1 输出 -0.41421 三分主要就是用于求函数极值，当然只用于求凸函数或者凹函数的极值。 尽管求这个东西可以通过对函数求导，再二分。。。嘤嘤嘤，但是对于有些麻烦的函数，求...

题目描述 农夫约翰的奶牛们喜欢通过电邮保持联系，于是她们建立了一个奶牛电脑网络，以便互相交流。这些机器用如下的方式发送电邮：如果存在一个由c台电脑组成的序列a1,a2,…,a©，且a1与a2相连，a2与a3相连，等等，那么电脑a1和a©就可以互发电邮。 很不幸，有时候奶牛会不小心踩到电脑上，农夫约翰的车也可能碾过电脑，这台倒霉的电脑就会坏掉。这意味着这台电脑不能再发送电邮了，于是与这台电脑相关的连接也就不可用了。 有两头奶牛就想：如果我们两个不能互发电邮，至少需要坏掉多少台电脑呢？请编写一个程序为她们计算这个最小值。 以如下网络为例： 1* / 3 - 2* 这张图画的是有2条连接的...

题目描述 有n个函数，分别为F1,F2,…,Fn。定义Fi(x)=Aix^2+Bix+Ci (x∈N*)。给定这些Ai、Bi和Ci，请求出所有函数的所有函数值中最小的m个（如有重复的要输出多个）。 输入格式 输入数据：第一行输入两个正整数n和m。以下n行每行三个正整数，其中第i行的三个数分别位Ai、Bi和Ci。Ai<=10，Bi<=100，Ci<=10 000。 输出格式 输出数据：输出将这n个函数所有可以生成的函数值排序后的前m个元素。这m个数应该输出到一行，用空格隔开。 输入输出样例 输入 3 10 4 5 3 3 4 5 1 7 1 输出 9 12 12 19...

题目复制乱码，就不复制了。 链接：落谷 P4014 很裸的一道二分图权值匹配，所以我们可以采用 KM 算法求解，但是我们还有一个更简单的算法，那就是费用流求解，我们建立一个超级源点S，和一个超级汇点T,让S连向人，让任务连向T，且费用都为0，流量为1. 然后根据输入的数据，对人和任务连线即可，就没了。。。。。 这道题数据很小就不用 ZKW 了，EK即可。。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> #define int long long using namespace std; const int N...

题目大意： 幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。每位小朋友应该怎样投票，才能使冲突数最小？ 明眼人应该能看出来是一个最小割的问题，为什么是最小割呢？ 因为题目要求两个集合，所以我们建立一个超级源点，和超级汇点，然后通过最小割，使得他们在两个不同的集合。 考虑建图： 我们让S连向睡觉的，不睡觉的连向T，反过来也行。 然后小朋友之间的关...

Ural大学有N名职员，编号为1~N。 他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。 每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。 现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。 在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。 输入格式 第一行一个整数N。 接下来N行，第 i 行表示 i 号职员的快乐指数Hi。 接下来N-1行，每行输入一对整数L, K,表示K是L的直接上司。 最后一行输入0,0。 输出格式 输出最大的快乐指数。 数据范围 1≤N≤6000, −1...