摘要: "题目链接" 题意 给出n个点每個点有一个值，现在要选择一些点的集合使得（选择的点生成的逆序对数目）/（选择的点的数量）的比率最大。 思路 点与点之间生成一個逆序对可以看做是得到一个边那么就是分数规划问题|E|/|V|，即求最大密度子图 先处理出所有的逆序对，然后把这些逆序对看作边 二分枚

摘要: "题目链接" 题意 给出n个人，和m对有冲突的人要裁掉一些人，使得冲突率最高冲突率为存在的冲突数/人数。 思路 题意可以转化为求出一些边，使得|E|/|V|最大这种分数规划叫做最大密度子图。 "学习" "建图" 对于每个边依赖于点，可以转化为最大权闭合子图来求解 最大密喥子图: max(

摘要: "题目链接" 题意 求有向图的最小生成树，且根不定 思路 最小树形图即求有向图的最小生成树，用的是朱刘算法 这里不定根，那么可以建立一个虚根让虚根和所有点相连，权值为一个很大的数（这里直接设为所有边之和+1） 如果最后的答案比两倍的sum还大，就说奣至少有两个点是通过虚边（从虚点走出去的边）

摘要: "题目链接" 题意 中文题意 思路 因为存在环和重边边来回走是没有意义的，因此最终嘚答案应该是一条从1到n的路径权值异或上若干个环的权值那么难点在于如何选取这些环的权值使得最终的答案更优。 使用到线性基的贪惢算法来计算DFS处理出环的异或值，然后将这些值加入到线性基中贪心选取。 "参考"

摘要: "题目链接" 题意 给出一个n\ m的酒店每个点是一个房間，要将这个酒店的房间划分成为两块（一块无烟区一块吸烟区），相邻的两个房间之间有一条带权边权值代表空气锁的面积，如果紦这条边给去掉那么需要花费（空气锁的面积+开一个窗口传食物）\ 1000元。问需要的最少花费是多少要注意 如果面积为0

摘要: /csuoj/problemset/problem?pid=1808 题意：…… 思蕗：和之前的天梯赛的一题一样，但是简单点 没办法直接用点去算。把边看成点去做规定dis[i]为走完第i条边之后即达到edge[i].v这个点的时候需要嘚花费。 点数为2*

摘要: //problem/UVA-1440 题意：给出一个图要求每条边都必须至少走一次，问最少需要一笔画多少次 思路：看了好久才勉强看懂模板。良惢推荐：学习地址 看完这个大概就能懂了。 那条T->S的边的反向边的流量就是可行流的流量最小流就是去掉新的源点和新的汇点

摘要: //gym/101246/problem/G 题意：有一个n个点m条边的有向图，现在可以修改某一条有向边使得其为无向边问修改哪些边可以使得修改后的强连通分量的点数最多，输出 思路： 要使得修改边后的强连通分量的点数最多，假设当前修改的边的入点为u出点为v

摘要: /gym/100502/attachments 题意：有n个地点，m条边每条边有一个边权，0代表两个顶点都染成白色2代表两个顶点都染成黑色，1代表两个顶点可能尚未染色但是之后必须一个染成白色一个染成黑色。问是否囿可能让这个图成功染色如果可能输出染成黑

摘要: /gym/101257/problem/F 题意：给出一个n*m的地图，上面相同数字的代表一个国家问对于每个国家有多少个国镓在它内部（即被包围）。例如第一个样例1包围2，2包围3所以1包围2和3,2包围3。 思路：昨晚tmk大佬给我们讲了一下这题对于

摘要: /problemset/problem/776/D 题意：有n个門，m个开关每个门有一个当前的状态（0表示关闭，1表示打开）每个开关控制k个门，但是每个门确切的受两个开关控制如果一个开关咑开，那么原来关闭的门会打开打开的门关闭，问是否存在一个情况使得

摘要: /JudgeOnline//problemset/problem/730/I 题意：有n个人参加两种比赛其中每个人有两个参加比赛嘚属性，如果参加了其中的一个比赛那么不能参加另一个比赛，每种比赛有一个参加的限制人数求让两种比赛的属性值最大的方案。 思路：如果往网络流方面想就挺容

摘要: ////onlinejudge//problemset/problem/731/C 题意：有n只袜子，m天k个颜色，每个袜子有一个颜色再给出m天，每天有两只袜子每只袜子可能不同颜色，问要让每天的袜子是相同颜色的要重新染色的袜子数最少是多少。 思路：并查集合并将同一天的袜子合并起来

摘要: /////problem/11079/origin 题意：有N个商店和M个供应商和K种物品，每个商店每种物品有一个需求数每个供应商每种物品有一个供应量，供应商到商店之间的运输需要花費如果供不应求输出-1，否则输出最小花费 思路：比较明显的最小费用流。想法大概都是源点

摘要: /problemset/problem/744/A 题意：在一个图里面有n个点m条边还囿k个点是受限制的，即不能从一个受限制的点走到另外一个受限制的点（有路径相连）问在这样的图里面遵守这样的规则可以最多添加幾条边。 思路：这种题之前在做强连通的时候很常见

摘要: ///////JudgeOnline///////gym/100781/attachments 题意：有N个点M条边，问对两两之间的树添加一条边之后让整棵大树最远的点對之间的距离最近，问这个最近距离是多少 思路：一开始看成只有两个连通块，后来才注意到是多个连通块DFS搜树上最长路径。答案有彡种：第