Yuki_fx

分类

未归档(69)

/ 注册

全部文章（共16篇）

HDU - 1875 畅通工程再续（并查集，最小生成树）

中文题目，一开始没有看清楚题目，WA了几发。一开始我以为是一旦有两个岛之间的距离不在 10-1000范围之内就不符合条件，输出oh！错了几次以后再看题目，原来是在符合条件的岛屿之间修路，如果不能使得全部岛屿连通的时候才输出oh！读题目很重要，读题目很重要，读题目很重要。还好这个是中文题...

图论最小生成树

2017-07-29

0 462

POJ 1232 Ubiquitous Religions（基础并查集）

并查集的基础题目，最简单套个模板就可以通过 #include<iostream> #include<cstdio> #include<cstring> #include<functional> #include<algorithm> i...

并查集图论

2017-08-07

0 407

HDU3718ZOJ3425 Similarity（The 2010 ACM-ICPC Asia Chengdu Regional Contest，加权二分图的最优匹配）

简单说就是求出两个字符串的相似程度。题目意思说的是学生得到一个任务，把不同物品分类，比如苹果，香蕉属于水果等，为了方便，给每个类别用字母编号。就得到题目中的字符串。每个学生的分类标准不一样，所以有不用的答案。现在问有多少个是正确的。最后结果是正确的答案除以总数。比如第一个样例，ABC 和...

图论二分图

2017-08-09

0 388

POJ 1861 Network (Kruskal算法)

这道题目其实是最小生成树的题目。但是题目给的样例有误导嫌疑，所以可能比较难的看出来。一开始读题目，看样例，看了很久，怎么对也好样例不一样。后面只好仔细在看一遍题目。发现题目讲的是，把任意两个点连通起来。那么这个就是最小生成树的定义。于是就按照最小生成树的样子写了一下。最后过了 ...

图论最小生成树

2017-08-18

0 442

HDU 1528&&ZOJ 2223 Card Game Cheater（二分图匹配）

Card Game Cheater________________________________________Time Limit: 10 Seconds Memory Limit: 32768 KB________________________________________ Ad...

图论二分图

2017-09-04

0 536

[ZOJ]2103 Marco Popo the Traveler（dfs+欧拉路）

题目意思就是马可波罗要去城市旅游，要求走遍所有城市之间的路一次且仅一次。这就是典型的欧拉回路，欧拉通路问题。属于图论中的欧拉图。题目有个附加条件，每两个城市之间最多只有一条高速公路，每条高速公路有颜色，只有汽车轮胎的颜色和路的颜色一样才可以通行。汽车轮胎的颜色可以更改，但只能在城市里面更改。...

图论欧拉图

2017-08-09

0 616

POJ 1258 Agri-Net

最小树模板题目，没有建图过程。题目给的就是邻接矩阵。题意：农夫要把各个农场的互联网连接起来。每个都有一定的费用。问最小费用。把题目抽象出来就是最小生成树。题目给的是邻接矩阵，发现是关于对角线对称的，无向图。可以用Prim算法。这里我Krustral和Prim算法都用了。 ...

最小生成树图论

2017-08-10

0 501

POJ 1325 Machine Schedule(二分图匹配)

题目大意：有两个机器A和B，A机器有n个模式，B机器有m个模式,两个机器最初在0模式然后有k个作业，每个作业有三个参数i，a，b i代表作业编号，a和b代表第i作业要么在A机器的a模式下完成【或者】在B机器的b模式下完成问两个机器总共最少变换多少次可以完成所有作业解题思路：很水的一个二...

图论二分图

2017-08-10

0 380

HDU1102 - Constructing Roads

最小生成树的简单题目；题目意思说的是有若干个村子需要连接，问最小费用解释一下输入数据就可以了先输入村庄的数量，村庄编号从1—N 接着输入两两村庄之间的距离，以邻接矩阵的形式给出。接着给出连接村庄的数量m，接下来m行表示这几个村庄相连这里我用的Krustral算法，先把连接的...

图论最小生成树

2017-08-11

0 451

HDU 1863 畅通工程

畅通工程系列题目用Krustral算法就可以过 #include<iostream> #include<cstdio> #include<cstring> #include<functional> #include<algorithm&g...

图论最小生成树

2017-08-11

0 408