#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false) #define endl '\n' using namespace std; typedef long long ll; const int maxn = 1e3 + 10; int vis[maxn], d[maxn], mat[maxn][maxn]; int n, cur, ans = 0; int main() { scanf("%d&q...

具体做法： 首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。 把所有边按权值从小到大排序 遍历每条边 如果这条边的两个顶点一个在树内一个在树外 则将顶点入树 保证了每条边的权值都是最小的 最终得到的树即为最小生成树 并查集的作用是判断两个顶点是否在一个集合（在一个树内）并且合并两个顶点到一棵树 假设排序后第一条边为从顶点i到顶点j权值为v的边，显然这条边是连通图中最短的边，那么可知这条边也是从i到j最短的边 #include<bits/stdc++.h> #define INF 0x3f3f...

#include<bits/stdc++.h> #define INF 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false) #define endl '\n' using namespace std; typedef long long ll; const int maxn = 1e5 + 10; typedef pair<int, int> p; vector<p>vec[maxn]; int vis[maxn]; int main() { ...

Floyd算法不能判断负环 算法思路 判断是否可以通过中转点 k 使 i 到 j 的距离减小 如图 设i-j为100 i-k为40 k-j为40 显然通过k的中转 从i到j所耗费的路程变短了 #include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false) #define endl '\n' using namespace std; typedef long long ll; const int maxn = 205; i...

优先队列实现对Dijkstra的优化 求单源最短路 #include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false) #define endl '\n' using namespace std; typedef long long ll; typedef pair<int, int>p; const int maxn = 205; int d[maxn]; int n, m; vector<p>vec...

Bellman-Ford算法用于求单源最短路包含负权边的问题，还可以检测图中是否有负环 #include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false) #define endl '\n' using namespace std; typedef long long ll; typedef pair<int, int>p; const int maxn = 205; int n, m; int d[maxn], ...

SPFA（Shortest path faster algorithm） 算法思想基于Bellman-Ford算法 进行优化的方式是 在进行某一次松弛操作中 如果起点到一个点的距离不变 那么以这个点为中转点能到达的点距起点的距离不变 如果这个点的距离发生了变化 就将这个点入队列 以求通过这个点中转的点距起点的位置是否发生了变化 vis数组标记当前位于队列中的顶点 显然 一个顶点出队列时 要取消标记 #include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sy...

给出两个字符串 求其最长公共子序列 #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<map> #include<cstdio> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' using namespa...

算法：动态规划＋二分查找 时间复杂度：O(nlogn) #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<map> #include<cstdio> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' usi...

这一场div2只A了两题 竟然加了70多分orz（肯定是基础分太低 A.Exercising Walk 题意: 向左走a步，向右走b步，向下走c步，向上走d步，问能否在执行所有操作的过程中始终处于题目给的范围内 思路: 只需判断同方向移动步数的代数和是否满足条件即可，注意特判下x1 == x2 和 y1 == y2的情况 这里我们用ta和tb代表一对相反方向的差 对于ta 为什么用b-a而不用a-b呢 可以这样思考 b-a为向右移动的步数 当b-a大于0时代表最终向右移动 此时x+ta恰好比x大 也代表向右移动 如果ta取a-b 就达不到这种效果 tb同理 当x1 == x2 时 在...

POJ 2431-Expedition 题意： 开车前往一个距离为l的城市，途中有n个加油站，每行驶一个单位的距离就会消耗一个单位的汽油，每到一个加油站都可以加油，问是否能到达目的地，能到达的话，最少需要加多少次油。 思路： 衷心提醒大家仔细看题！！！！！！ 输入的距离不是距起点的距离，而是距终点的距离(白WA3发血亏），而且不一定按顺序给出，需要进行排序，所以用结构体还是比较方便的。 我们可以这样想，既然路过的每个加油站都可以加油，意思就是“经过一个加油站就获得了在之后任何一个时间加油的权力”。 为了最小化加油的次数，我们只有在必须加油的时候才加油，并且加油的量应该是途径的所有加油...

POJ 1182-食物链 题意： 动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。 现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物链关系进行描述： 第一种说法是"1 X Y"，表示X和Y是同类。 第二种说法是"2 X Y"，表示X吃Y。 此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。 1） 当前的话与前面的某些真的话冲突，...

A. Candies 题意 给定一个整数，判断是否存在 思路 先对公式进行预处理 明显是一个等比数列 化简后得到 因为答案一定存在 所以用快速幂从小到大枚举即可 #include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include&lt...

C. Permutation Game 题意： 一个线性的棋盘，上面有n个格子编号为1-n，当棋子所在位置满足以下情况时，可以移动 1.新格子的数值必须严格大于旧格子 2.移动的距离必须是旧格子中数字的整数倍 谁不能采取行动，谁就输了，即当前棋子位于一个不能移动的位置 求哪些出发格子可以使Alice必胜 思路 记录每个点下一步能到达的点，建反图然后拓扑 如果一个点标记为0代表必输点，为1代表必赢点，-1表示还没判断 对每一个入度为0的点，即没有可到达的下一个点的点进行判断 如果点u是必输点，说明无法进行下一步操作，所以，能到达这一点的点一定是必赢点，因为从必赢点跳到这一点，对手就无法...