CHL的博客

分析：将每一个连通块的所有点都指向该连通图的最大点。从1点开始遍历，假设fa[1] = x;那么从2~(x-1)的所有点的根结点都应该指向x(同属于一个连通块)。如果此时有一个点的根结点是y，不是x,那么就需要添加一条边将这两个连通块连起来了。这时候从2开始到max(x,y),根结点一定都是指向max(x,y),所以x的值要选择大的，避免两个连通块有重复的。之后重复进行该种操作即可统计出最后的答案...

分析：利用并查集处理每一条边上两点的关系。假设两个点已直接或间接可互达，在此之外又连有额外的边，那么该条边应该被重建（集合合并问题）。#include<bits/stdc++.h>using namespace std;const int N = 1e3 + 5;typedef pair<int, int> P;int fa[N], Rank[N];int ...

思路：先建双向边：鳄鱼与鳄鱼之间(若距离<=d)，圆心与鳄鱼之间(距离-7.5<=d)，汇点(n+1)与鳄鱼之间建边(从鳄鱼的坐标能到边界)跑0~n+1的最短路，因为本题卡精度!!! 所以abs(a-b)<=eps;判相等#include<cstdio>#include<vector>#include<queue>#incl...

题意：给你一个长度为n的序列，看成是图上的n个结点，如果结点i,j连通当且仅当ai & aj != 0，问形成的图是否成环，且最小的环的大小是多少？思路：我们考虑最大长度不构成环的n，1 1 2 2 4 4 8 8 ...2^63-1 2^63-1，发现n最大是128(前提是序列中的数都不为0)，说明超过128一定存在一个环，且环的大小为3.n<=128时，建图跑Floyd求最小...

/*问题：求树的直径方法：树形DP*/#include<cstdio>#include<algorithm>using namespace std;const int N = 5e4 + 5;struct edge { int to, nex, wi;} es[N << 1];bool vis[N];int head[N], di...

题意：给你n个点m条边（单向边）和q次操作，初始时所有点都是没有标记的，有两种操作： 1. 0 x：将x标记，如果已近标记过了就输出 “ERROR! At point x” 2. 1 u v ：询问从u到v的最短路，并且要求都是被标记过得点，否则输出 “ERROR! At path x to y” ，如果到不了就输出 “No such path” ，有就输出最短路径大小分析...

思路:建立超级源点0，向每个相邻的城市建一条边权为0的边，跑最短路。注意，数据中有存在自环的情况，特判一下#include<cstdio>#include<queue>#include<algorithm>using namespace std;const int N = 1e3 + 5;const int Inf = 1e9;typedef ...

思路：对两个可互相到达的楼层建边，跑最短路#include<cstdio>#include<queue>#include<algorithm>using namespace std;const int N=2e2+5;const int Inf=1e9;typedef pair<int,int> P;vector<P>...

题意：n个点m条边，构成的图无环且不一定是一个连通图，q次询问两点间的最短距离思路：因为给的图其实是一棵树，所以本质上是LCA，套用模板预处理点与点之间的父子关系。将属于同一棵树内的点并到一个点集里，在判断两点的最短路径前先判两点是否在同一点集里。#include<cstdio>#include<algorithm>using namespace std;c...

思路;首先,我们可以想到可以把每门课程的每个等级都看成一个点,然后我们可以知道对于同一门课程,高等级向低等级走花费为0.因此我们可以直接用每个课程每个等级建图,然后将每门课程的高等级向低等级连一条权值为0的边.对于辅导班,我们可以直接连接对应的课程和等级...那么对于虚根呢..其实我们很容易想到.虚根应该与每门课程等级为0的点相连.权值直接设计为0即可#include<iost...

思路：先制造一个虚拟结点：它向所有结点连一条边，权值要大于原图中所有权值的和，以它为根跑最小树形图，如果ans >= 2 * sum，那么说明从虚拟结点连出去两条以上的边，即原图不连通，反之原图必联通，且权值和为ans - sum。根节点就是树形图上虚拟节点的边指向的那个结点#include<iostream>#include<cstdio>#include...

基础并查集#include<iostream>#include<cstdio>#include<set>using namespace std;const int N=1e3+5;int fa[N],n,k;int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]);}void Merg...