POJ2449 - Remmarguts' Date

HDU2376 & HDU5723

(封面图与内容完全无关，只是因为图好看才放上来)

HDU2464 - A Pair of Graphs

A Pair of Graphs 一道同构图的题目。大意就是给出两幅图，同时可以执行两种操作，分别是加边和删边，在A图上加边、删边的代价是Ia，Da；在B图上加边、删边的代价是Ib，Db。现在要通过这两种操作使得两幅图同构，问怎样的操作代价最小，求这个最小代价 因为数据范围很小，N<=8，所以可以直接枚举。具体见代码 #include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <list> #include <set> #in..

HDU3926 - Hand in Hand

Hand in Hand 题目大意是给你两张图，让你判断这两张图是否同构，条件是两张图上的点最多都只有两个度数，可以看作是一个简单的同构图问题。 首先说一下什么是同构图 按字面意思理解，同构图即为"相同结构的图"，用图论中的术语描述就是 >图论当中的术语，假设G=(V,E)和G1=(V1，E1)是两个图，如果存在一个双射(即一一映射)m：V→V1，使得对所有的x,y∈V均有xy∈E等价于m(x)m(y)∈E1，则称G和G1是同构的,这样的一个映射m称之为一个同构 而我对于同构图的理解是，一个同构图，应具有相同的连通性，链/环的个数以及链上/环上的点的个数应相同，点与点、边与边之间的对应关系应相同 比方说，下面的就是一对同构图 左图是一个只由五元环组成的图，而右图看起来和左图很不一样，但实际上也是一个..

POJ3687 - Labelling Balls

Labeling Balls 一道拓补排序的题，虽然a了但是是看题解过的......存在的疑问已在注释中标明

HDU2647 - Reward

Reward 其实就是用拓补排序判一下环，但需要注意两点：一是反向建图。这主要是为了计算奖金时的方便，因为反向建图就可以从奖金最少的那个人出发，遍历整个图，逐步累加得到答案；如果是正向建图，则需要先找到奖金最少的那个人，将他作为起点......二是这道题其实是根据每个点(人)在图中的深度来确定每个点(人)的奖金的。已下图为例： 3和4的深度是一样的，所以两者的奖金也一样。因此，不能简单地认为，如果可以拓补排序了，答案就是888 + (n * (n - 1)) / 2 代码如下: #include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <a..

HDU1811 - Rank of Tetris

Rank of Tetris   根据题单的提示，这是一道拓补排序+并查集的题目，然而我并不会拓补排序......所以这里先写一下拓补排序相关的东西吧......   首先，拓补排序是对一系列有先后顺序的“活动”的排序。何为“有先后顺序的‘活动’”？举个例子，假如现在某人要穿衣服，那他必须要先穿内衣再穿中间的毛衣，最后再穿外套。拓补排序就是使用有向无环图(DAG)来对这些有先后顺序的活动进行排序，得到一个可行的顺序。对于同一系列的活动，可能有多于一种顺序可以使他们满足拓补排序。这跟穿衣服时可以先穿裤子再穿毛衣然后再穿外套，也可以先穿毛衣再穿裤子然后穿外套是一样的。   拓补排序的实现：先找出入度为0的点，然后将这个点以及与这个点相连的边删除，并将与这个点直接相连的点的入度都减一。再找出当前入度为0的点，重..

欧拉路、欧拉回路与Fleury算法

一、概念解释 欧拉路：给定无孤立结点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路。 欧拉路的存在条件：没有孤立结点，同时奇数度数的点只有2个或0个。 欧拉回路：若一个连通图中没有奇数度数的点，则该图中一定存在一条起点与终点重合的欧拉路，称为欧拉回路。   通俗地讲，欧拉路就是一笔画游戏，每条边只能走一次，问怎么画才能把所有边都画出来。欧拉回路就是在此基础上，不仅要把所有边都画出来，还要求起点和终点要是同一个地方。 二、判断欧拉路是否存在   要判断欧拉路是否存在，只需要判断奇数度数的个数即可。一般使用并查集来实现。代码如下： //判断欧拉路是否存在 #include <iostream> #include <cstdio> #include <cstrin..

POJ2236 - Wireless Network

Wireless Network 一道并查集模板题。

HDU1301 - Jungle Roads

Jungle Roads 套用Kruskal或Prim的模板即可。这里我用的时Kruskal。