ProApe

分类

OJ题(25) 数据结构(7) 算法(4)

/ 注册

全部文章（共36篇）

STL之栈(链表实现)

1 1实验项目二栈的基本操作及其应用截止时间：11月17日23:59 课程名称：数据结构实验目的： 1．掌握栈的定义及实现； 2．掌握利用栈求解算术表达式的方法。实验要求： 1、使用链式存储结构完成栈的各种基本操作； 2、补充完成In©, Preced(t1,t2),Operate(a...

2020-01-02

0 981

STL之队列(链表实现)

1 实验项目三：队列的基本操作应用截止时间：11月14日23:59 课程名称：数据结构实验目的： 1．掌握队列的定义及实现； 2．掌握利用队列的基本操作。实验要求： 1、使用链式结构完成队列的各种基本操作； 2、补充完善教材81页的舞伴问题。实验项目名称：队列的基本操作应用实验过程：...

2020-01-02

0 709

Warshall算法求有向图的传递闭包

1定义是这样给出的，传递闭包：对于任何关系 R，R 的传递闭包总是存在的。传递关系的任何家族的交集也是传递的。进一步的，至少存在一个包含 R 的传递关系，也就是平凡的: X × X。R 传递闭包给出自包含 R 的所有传递关系的交集……其实就是求点与点之间的可达关系，比如1–>4,4–>6...

2020-01-02

0 1666

Floyd算法计算最短路并记录路径

1计算最短路有弗洛伊德和迪杰斯塔拉两种算法，前可以计算出任意两个顶点之间的最短路径，后用于计算特定两个顶点之间的最短路径，Floyd算法用于计算无向或者有向图加权图（不包括长度为负的回路）的完全最短路径 2Floyd算法的构造过程和Warshall算法非常相似，通过初试的权重矩阵，每次加入一个顶点...

2020-01-02

1 1998

洛谷P2661 信息传递

1这使我意识到提高组有些题难就难在他的算法标签是隐晦的，读完题，感觉除了暴力就没有其他想法了……看了题解，才知道原来是求有向图中最小的环，仔细想想还真是的 #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace ...

2020-01-02

0 576

有向图求最小环

1 先用拓扑排序将多余的顶点去除，只剩下组成环的点，然后用DFS求出每个环的长度 #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; #define pi acos(-1.0) #define e...

2020-01-02

0 785

洛谷P1330 封锁阳光大学

按照题意，每个顶点要不放河蟹，要不不放河蟹，而且相连的顶点不能具有相同的状态。因此我们可以将其抽象成二分图，即两种相连的顶点不能染成相同的颜色，对于每一个连通图，我们使用两种颜色通过DFS将其染色，只要有一个连通图不能染色成功，就直接得到结果“NO”,因为题中可能含有多个连通图，对第i个连通图，我用...

2020-01-02

0 583

HDU Wave

我们发现这道题的C很小，所以得从这方面下手，把这些数依据奇偶性划分成两个集合，并且把每一个数在序列中出现的位置记录下来，我们暴力尝试每一个奇数和偶数构成的Wave，最后取一个最大值就行了，每一次尝试过程是这样的的比如：N<mark>8 C</mark>2 2 1 1 2 2 ...

2020-01-02

0 500

HDU Traffic

题意是这样的：在一个十字路口，有N辆车是东西通行的，有M辆车是南北通行的，并且给你每辆车通过的十字路口的时刻表，当东西通行的车和南北同行的车同时通过十字路口的话就会发生碰撞，现在要求东西通行的时刻表不变，南北通行的车辆要集体最少等待多少时间才能不发生碰撞一开始题读错了，忽略了集体等待，好吧，其实是我...

2020-01-02

0 451

HDU Cotree(换根dp,树的重心)

我是看了这位大佬的博客，感谢大佬他的博客题目描述：有两颗树，需要在这两棵树之间添加一条边，这样就变成了一棵树，求这棵树任意两点之间的最小距离和即$$\sum ^{N}{i=1}\sum ^{N}{j=i+1}dis\left( i,j\right)$$ 解题思路：首先考虑，我们要在哪两个点...

2020-01-02

0 768