搜索与图论
练习：https://www.luogu.com.cn/problem/list?tag=126,127&page=1&orderBy=difficulty&order=asc
https://www.luogu.com.cn/training/204#problems
存图
邻接表：
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);
BFS：队列维护
==“最短路”==
DP：无环最短路
所有边权为1——>BFS
void bfs(int root){
queue<int>q;
vis[root]=1;//已被遍历
q.push(root);
while(!q.empty()){
int t=q.front();
q.pop();
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(!vis[j])
vis[j]=1,q.push(j);
}
}
}
DFS：递归
空间要求高，思路难想
回溯：回复状态
剪枝：判断不合法，断后路
搜索顺序
int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];//存路径
//表示该状态已被访问
if (!st[j]) dfs(j);
//dfs之后回复状态
}
}
拓扑排序
最短路
据数据范围判算法，看复杂度
有负权回路不一定存在最短路
抽象建图
找最短的最短路
1. 从起点出发，找最短的路（直达）
2. 找次短路（直达或经1.转）
单源最短路
- 所有边权都是正数
朴素Dijkstra
O(n^2+m)
邻接矩阵存
int a[N][N],d[N][N];
bool vis[N];
int dijkstra(){
memset(d,0x3f,szieof d);
d[1]=0;//初始化距离，起点为0，其余都为无穷
for(int i=0;i<n-1;i++){
//未确定最短路的点中，寻找距离最小的点
int t=-1;
for(int j=1;j<n-1;j++)//除去自身
if(!vis[j]&&(t==-1||d[t]>d[j]))
t=j;
//用t更新其他点的距离
for(int j=1;j<=n;j++)
d[j]=min(d[j],d[t]+a[t][j]);//松弛操作
vis[t]=true;
}
if(d[n]==0x3f3f3f3f)
return -1;
return d[n];
}
堆优化Dijkstra
O(mlogn)
邻接表存
优先队列维护距离
typedef pair<int,int>PII;
int n,i;
int h[N],w[N],e[N],ne[N],dis[N];//邻接表存边，距离数组
bool vis[N];
int dijkstra(){
memset(dis,0x3f,sizeof dis);
dis[1]=0;
priority_queue<PII,vector<PII>,greater<PII>>heap;
heap.push({0,1});//first存距离，second存节点编号
while(heap.size()){
auto t=heap.top();
heap.pop();
int ver=t.second,distance=t.first;
if(vis[ver])
continue;
vis[ver]=true;
for(int i=h[ver];i!=-1;i=ne[i]){
int j=e[i];
if(dis[j]>distance+w[i]){
dis[j]=distance+w[i];
heap.push({dis[j],j});
}
}
}
if(dis[n]==0x3f3f3f3f)
return -1;//不存在就返回-1
return dis[n];
}
- 存在负权边
Bellman-Ford
O(nm)
记得备份！
使用情况：经过最多不超过k条边的最短距离
怎么存边都行
int n,m;
int dis[N];
struct Edge{
int a,b,w;
}edges[M];
int bellman_ford(){
memset(dis,0x3f,sizeod dis);
dis[1]=0;
// // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
int a=eddges[j].a,b=edges[j].b,w=edges[j].w;
if(dis[b]>dis[a]+w)
dis[b]=dis[a]+w;
}
if(dis[n]>0x3f3f3f3f/2)
return -1;
return dis[n];
}
//三角不等式：dis[b]<=dis[a]+w
SPFA
一般O(m),最坏O(nm)
途中含负环
网格状易被卡
队列优化，更新过的（变小点）来更新别的点
int n;
int h[N],w[N],e[N],ne[N],i;
int dis[N];
bool vis[N];
int spfa(){
memset(dis,0x3f,sizeof dis);
dis[1]=0;
queue<int>q;
q.push(1);
vis[1]=true;
while(!q.empty()){
auto t=q.front();
q.pop();
vis[t]=false;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dis[j]>dis[t]+w[i]){
dis[j]=dis[t]+w[i];
if(!vis[j])
q.push(j),vis[j]=true;
}
}
}
if(dis[n]==0x3f3f3f3f)
return -1;
return dis[n];
}
SPFA判是否存在负环 O(nm)
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中
// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
// 不需要初始化dist数组
// 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
queue<int> q;
for (int i = 1; i <= n; i ++ )
{
q.push(i);
st[i] = true;
}
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
多源汇最短路
Floyd
O(n^3)
原理：DP
//初始化：
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
最小生成树
稠密图用朴素prim，稀疏图用Kruskal
prim算法
朴素O(n^2)、堆优化 (基本不用)
关键：==集合==版的dijkstra
- 找集合外距离集合最近的点，用t更新
- 点到集合距离：点到集合内任意一点的最小距离
//省去定义过程，邻接矩阵存边，dis[]表示点到集合的距离
int prim(){
memset(dis,0x3f,sizeof dis);
int res=0;
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++)
if(!vis[j]&&(t==-1||dis[t]>dis[j]))
t=j;//更新
if(i&&dis[t]==INF)
return INF;//图不连通
if(i)
res+=dis[t];
vis[t]=true;
for(int j=1;j<=n;j++)
dis[j]=min(dis[j],a[t][j]);
}
return res;
}//先累加，再更新
Kruskal算法
O(mlogm)
1. 边按权重升序排序
2. 枚举边：不连通就加入集合（并查集判）
- 结构体存边（存的时候重载，放入输入中固定两点之间最小的边）
-
int n,m;
int fa[N];
struct Edge{
int a,b,w;
bool operator<(const Edge&W)const{
return w<W.w;
}
}edges[M];
void init(){
for(int i=1;i<=n;i++)
fa[i]=i;
}
int find(int x){
if(fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
int kruskal(){
sort(edges,edges+m);
init();
int res=0,cnt=0;
for(int i=0;i<m;i++){
int a=edges[i].a,b=edges[i].b,w=edges[i].w;
a=find(a),b=find(b);
if(a!=b){
fa[a]=b;
res+=w;
cnt++;
}
}
if(cnt<n-1)
return INF;
return res;
}
二分图
染色法
O(n+m)判二分图
- 二分图：当且仅当图中不含奇数(边)环
- 当图中不含==奇数环==，没有染色矛盾
- 一个点确定颜色后，其余的都能确定了（左右端点不同色）
- dfs实现染色过程，邻接表存图
int n;
int h[N],e[M],ne[M],i;
int color[N];//-1未染色，0白色，1黑色
bool dfs(int u,int c){//u当前节点，c当前颜色
color[u]=c;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(color[j]==-1)
if(!dfs(j,!c))
return false;
else if(color[j]==c)
return false;
}
return true;//完全没有颜色冲突
}
bool check(){
memset(color,-1,sizeof color);
bool flag=true;
for(int i=1;i<=n;i++)
if(color[i]==-1)
if(!dfs(i,0)){
flag=false;
break;
}
return flag;
}
匈牙利算法
O(mn)
- 两集合匹配（单一匹配，失配则回溯，换对象）
int n1,n2;
int h[N],e[M],ne[M],i;//一到二，只存单方向的边
int match[N];//第二个集合中的每个点当前匹配的的点是哪个
bool vis[N];
bool find(int x){
for(int i=h[x];i!=-1;i=ne[i]){
int j=e[i];
if(!vis[j]){
vis[j]=true;
if(match[j]==0||find(match[j])){
match[j]=x;
return true;
}
}
}
return false;
}
//求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res=0;
for(int i=1;i<=n1;i++){
memset(vis,false,sizeof vis);
if(find(i))
res++;
}
