Coroalla_Virus-CSDN博客

原创利用 fdisk进行分区

1):fdisk命令参数 p:打印分区表. n:新建一个新分区. d:删除一个新分区. q:退出不保存. w:退出且保存.例子:先看下磁盘:root@archiso ~ # lsblk在这里对磁盘sda进行分区.规划的是分一个主分区,大小为1G,分三个逻辑分区,大小为2G ,2G,5G.root@archiso ~ # fd

2016-05-28 10:57:50 18574

原创 HDU 5652 India and China Origins(并查集)

题意：中国和印度之间有一片地方，把这片地方抽象化，于是就可以看成一个N * M矩阵，其中黑色的代表高山不能走过去，白色的代表平原，可以通行，人每次可以选择往上下左右四个方向移动，但是随着时间的变化某些白色的平原会变成黑色的高山，从而变为不可通行，题目中给出一个代表地势的图，然后有 Q 次操作，第 i 次操作代表在第 i 年（x, y）处的平原变成了高山，即白色变为了黑色。问中国

2016-04-04 10:01:00 532

原创 UVA 10600 ACM Contest and Blackout(最小生成树)

题意：给你点和边，求出最小生成树和次小生成树。思路：先求一次最小生成树，然后标记每一条边，依次删除，再求最小生成树，从中找到最小的就是次小生成树了。代码： import java.util.Scanner;import java.util.Comparator;import jav

2016-04-03 13:01:44 516

原创 UVA 10369 - Arctic NetWork (求最小生成树)

题意：在南极有 N 个科研站，要把这些站用卫星和无线电连接起来，是的任意两个之间都能互相通信，如果其中任意的一个地方安装了卫星，那么就可以和其他安装卫星的互相通信，和距离没有关系，但是安装无线电是需要费用D的，这个费用 D 为在安装无线电的地方中使用的无线电通信花费最大的那个值。现在有S个卫星可以提供给你安装，还有足够多的无线电设备，让你设计一个方案，使得D的费

2016-04-03 12:50:26 397

原创 UVA Live 6437 Power Plant 最小生成树

题意：有许多油井和村庄什么的，让你使得这些村庄能连通一个油井就好了。第一行给你一个数字T代表有T组测试数据，第二行有 M , N , K ，M代表包括油井在内的村庄数，N 代表有N个两两连通的地方。K代表有K个油井。接下来有N行，每行三个数 u , v, w, 代表 u 号和 v 是连通的权值为 w。思路：以往做的题目都是只有一个源点，这道题油井的数目就是源点，所以源点不唯一。但是不要想复

2016-04-03 11:31:02 414

原创 UVA 1151 Buy or Build MST

题意：在平面上有n个点，要让所有n个点都连通，所以你要构造一些边来连通他们，连通的费用等于两个端点的欧几里得距离的平方。另外还有q个套餐，可以购买，如果你购买了第i个套餐，该套餐中的所有结点将变得相互连通，第i个套餐的花费为ci。求最小花费。解决：在这里我们可以采取枚举所有可能 + K算法来得出答案，比如这里有三个套餐，我们利用二进制枚举001 010 011 100 101 110 11

2016-04-03 10:22:56 451

原创 UVA 1395 Slim Span 最小生成树

题意：给你一个图，让你求这个图中所有生成树中满足题目条件的，这个条件是生成树中最长边与最短边的差值最小。思路：根据最小瓶颈生成树的定义：在一个有权值的无向图中，求一个生成树最大边的权值尽量小。那么我可以从小到大枚举每一条边作为我所求生成树的最短边（即第一次以最短边求最小生成树，第二次删除第一条边，以第二条边为最短边求最小生成树，第三次删除第一条边和第二条边，以第三边为最短边求最小生成树。）然后

2016-04-02 20:56:21 835

原创 POJ 1679 The Unique MST 次小生成树

题意：判断最小生成树是不是唯一，我的判断方法是求次小生成树，如果相等那么说明不唯一。/* POJ 1679:判断最小生成树是否唯一思路：先求出最小生生成树 MST，再求出次小生成树SST，判断是否相等。求SST：先求最小生成树，标记构成最小生成树的每一条边，然后依次删除，再次求最小生成树，取这里面的最小的即是次小生成树算法实现：kruskal 错误：删除一条属于MST的边

2016-04-02 20:30:12 347

原创 POJ 1789 Truck History

题意：题意比交难理解，直接描述了，说这里有一些字符串，一个字符串必须由另外一字符串 “衍生” 出来，衍生的价值是这两个字符串之间的 distance 距离，即俩个字符串的相同位置总共有几个字符不一样。比如 aaaaaaa 和 baaaaaa的 distance 距离为 1；跟你 N 个字符串，让你给出一个衍生方案，是的最后的衍生价值最小。思路：这道题可以转化为求最小生成树的一道题，每个

2016-04-02 18:52:28 279

原创 POJ 1258 Agri-Net 最小生成树

题意：给出一个N。接下来有一个N * N的邻接矩阵A，第 i 行第 j 列代表点 i 和 j 相距A[i][j].求连同所有点的最短路径，求最小生成树即可。思路：用P算法，直接用邻接矩阵来存放数据就好了。import java.util.Scanner;public class Main { final static int MAXN = 100 + 3; final

2016-04-02 17:34:18 268

原创 POJ 1251 Jungle Roads

题意：第一行给一个N，代表这里有N- 1 个村庄，接下来有 N- 1 行，每行开头输入一个大写字母 C 代表第 i 个村庄的编号，随后有一个数字 m 代表 C 这个村庄和 m 个村庄相连，随后再给出 m 组数据，每组输入由一个大写字母 F 和数字 w 组成，代表 C 和 F 之间的距离为 W；当N== 0时程序结束。思路：因为题目中给出的字母为 A - Z 那么我这里用数字 1 - 26代

2016-04-02 17:27:41 327

原创 HDU 1879 继续畅通工程最小生成树

思路：比较典型的求最小生成树，利用K算法或者P算法，如果在输入时两个村庄的修建状态为已修建，那么我这里的做法是让他们之间的权值为 0，即修建费用为 0；然后套用算法就好了。代码P算法：#include #include #include #include #include #include #include #include #include #include #

2016-04-02 17:15:21 312

思路：题目给的是每个小岛的坐标，俩个岛之间的距离等于俩个岛之间的欧几里得距离，然后套用P算法或者K算法就好了。用K算法或者P算法都可以，但是这道题显然需要计算出来每俩个岛之间的距离，这样就有接近V^2/2条边，输入稠密图，所以用P算法会更好点。注意的是题目中说两个岛之间的距离不能大于1000米也不能小于10米，如果用P算法那么如果俩个岛之间的距离不符合条件就把这个到之间的距离设置为无穷大，如果用的

2016-04-02 10:49:16 360

原创 HDU 1863 畅通工程最小生成树

思路：比较典型的最小生成树的题目了、、在这里用求最小生成树的经典算法K(Kruskal)算法和P（Prim）算法。我的 K 算法用的是结构体来存图，P 算法用的是邻接矩阵来存图，K算法的复杂度是O(ElogE)，比较适用于稀疏图，P算法的复杂的是O（V ^ 2）,适合用稠密图。以下是C++的K算法代码#include #include #include #include #

2016-04-02 10:30:44 341

原创 CodeForces 445B DZY Loves Chemistry （并查集）

题意：有N种药剂编号 1 ~ N，然后又M种反应关系，这里有一个试管，开始时危险系数为 1,每当放入的药剂和瓶子里面的药剂发生反应时危险系数会乘以2，否则就不变，给出M种反应关系，求最大的危险系数。思路：我们假设 1 ~ N 有 M 种反应关系，若果有反应关系的我们可以把他们看成是一个集合，假设这M种反应构成了 T个集合，那么把这T个集合依次放入试管，有几个不发生反应呢？当然是T个了

2015-11-08 15:34:28 338

原创 UVA 11987 Almost Union-Find (并查集)

题意：这里有N个数编号1 ~N，开始每个数各自在一个集合里面，然后有三种命令：1 P Q ：把 P 所在的集合和 Q 所在的集合合并，如果已经在一个集合里面了就忽视2 P Q ：把 P 这个元素从它所在的集合里面拿出来放到 Q 里面，，如果已经在一个集合里面了就忽视3 P ：询问 P 所在集合元素的个数和P所在集合元素的和。思路：对于命令 1 直接合并就好了，用cnt[]

2015-11-08 15:14:30 353

原创 UVALive（LA） 4487 Exclusive-OR（带权并查集）

题意：对于n个数X[0]~X[n-1]，但你不知道它们的值，通过逐步提供给你的信息，你的任务是根据这些信息回答问题，有三种信息如下：I p v ： Xp = v; Xp 的值为vI p q v : Xp ^ Xq = v; Xp 异或Xq的值为vQ k X1 X2 X3 ..... Xk : 问X1异或X2异或X3....异或Xk的值为多少？解题思路

2015-11-08 11:26:35 474

原创 UVALive 3027 Corporative Network （带权并查集）

题意：有 n 个节点，初始时每个节点的父节点都不存在，你的任务是执行一次 I 操作和 E 操作，含义如下：I u v : 把节点 u 的父节点设为 v ，距离为| u - v | 除以 1000 的余数。E u : 询问u 到根节点的距离。解题思路：因为题目只查询节点到根节点的距离，所以每棵树处理根节点不能换之外、其他节点的位置可以随意改变，这恰好符

2015-11-08 11:23:54 379

原创 UVALive（LA） 3644 X-Plosives （并查集）

题意：有一些简单化合物，每个化合物都由两种元素组成的，你是一个装箱工人、从实验员那里按照顺序把一些简单化合物装到车上，但这里存在安全隐患：如果车上存在K个简单化合物，正好包含K种元素，那么他们就会组成一个容易爆炸的混合物，为了安全起见，每当你拿到一个化合物时，如果它已经和已装车的化合物形成了易爆混合物，你就应该拒绝装车，否则就应该装车，输出你拒绝了多少个混合物。思路：一种化合物由两种元素组成，

2015-11-08 10:35:10 416

原创 POJ 2524 Ubiquitous Religions （并查集）

Description当今世界有很多不同的宗教,很难通晓他们。你有兴趣找出在你的大学里有多少种不同的宗教信仰。你知道在你的大学里有n个学生(0 。你无法询问每个学生的宗教信仰。此外,许多学生不想说出他们的信仰。避免这些问题的一个方法是问m(0 <= m <= n(n - 1)/ 2)对学生,问他们是否信仰相同的宗教( 例如他们可能知道他们两个是否去了相同的教堂) 。在这个数据

2015-11-08 10:22:49 305

原创 POJ 1611 The Suspects (并查集)

Description严重急性呼吸系统综合症( SARS), 一种原因不明的非典型性肺炎,从2003年3月中旬开始被认为是全球威胁。为了减少传播给别人的机会,最好的策略是隔离可能的患者。在Not-Spreading-Your-Sickness大学( NSYSU), 有许多学生团体。同一组的学生经常彼此相通,一个学生可以同时加入几个小组。为了防止非典的传播,NSYSU收集了所有

2015-11-08 10:13:24 313

原创 HDU 1558 Segment set（并查集）

题意：给你一些线段的起点和终点的坐标，最后问和某个线段相连的或者间接相连的线段有多少个（包括本身）？P X1 Y1X2 Y2 起点（X1,X2）终点（X2,Y2）；按照出现次数依次编号为1,2,3,4......Q N 问和第N个线段相交或者间接相交的线段有多少个，所谓间接相交就是如果 1 和 2相交， 2 和 3相交那么 1 和 3 就是间接相交。。。。。解题思路：每

2015-11-08 09:07:32 270

原创 HDU 1856 More is better (并查集)

题意：给你两个数代表这两个人是朋友，朋友的朋友还是朋友~~，问这些人组成的集合里面人最多的是多少。。。思路：属于并查集了，我用的是带路径压缩的，一个集合里面所有元素（除了根节点）的父节点都是根节点，最后统计下哪个根节点出现的次数最多就OK了~~#include #include #include #include #include #include #include usin

2015-11-08 09:03:09 348

原创 HDU 1325 Is It A Tree?（并查集）

题目大意：给你两个节点，前者指向后者（可以认为前者是后者的父节点），然后让你判断是否是一棵树。解题思路：先说说这道题和小希的迷宫（HDU1272）那道题的区别，前者给出的两个点是有方向的，而后者是没有的，这就是唯一的区别。再者这道题其实就是让你判断所有的点最后所形成的图是否是一棵树。做这道题时错误了很多遍，细想之，主要是开始思路不好，很容易乱，理清思路让代码变得清晰起来就好了。判断一个图是否为

2015-11-07 20:34:22 421

原创 HDU 1272 小希的迷宫（并查集）

题目：中文的~~~~思路：属于并查集算法，输出YES的条件有两个，第一：每次新输入的两个数不能同属于一个集合（即根节点一样），第二：所有的输入完成后判断是否仅有一个集合（根节点只有一个）。只有这两个条件全部达成，才能输出“YES”~~~需要注意的是直接输入“0 0”，应该输出“YES”。#include #include #include #include #includ

2015-11-07 20:27:13 238

原创 HDU1232 畅通工程 (并查集)

题目：中文的就不说了~~~~思路：属于并查集的基础题，比较典型，可以把连通在一起的看成是一个点，假设一共有N个独立的点，那么就需要 N - 1 条边把他们连通起来，所以利用并查集算法，最后统计有多少个独立的集合，然后把这个数减去一便是我们所要的答案了~~~~#include #include #include #include #include #include #in

2015-11-07 19:44:30 283

原创 HDU1213 How Many Tables （并查集）

题目大意：有一个人要过生日了，请他的朋友来吃饭，但是他的朋友互相认识的才能坐在一起，朋友的编号从1 ~ n,输入的两个数代表着这两个人之间有关系。问需要多少桌子。思路：并查集的基础题目，pre数组存的是父节点的值，root数组代表是否为根节点。最后统计根节点的数量就可以了~~~~~#include #include #include #include #include #in

2015-11-07 19:31:58 258

Ash.的博客