三、搜索与图论
(一).DFS
简介：通过系统的模拟栈实现，“走头无路”才往回退，不具最短性。回溯是该算法的关键。
1.全排列问题 (AcWing 842.排列数字)
(1)算法思想：
递归函数：假设求n=3时的全排列，函数入口为位置u（u从path数组第0号位置开始，当u为3时说明数组中0,1,2三个位置都有数字，所以该输出了），设置一个数组path[]依次记录每一位的数字，当第3个位置有数字时就该输出该组合同时返回该函数，否则依次将未被使用过的数字加入path中，该循环的结束条件应该为i=3，然后再递归调用下一个位置，直到递归到第3个位置时返回（此时已达到最深部，即可回溯）（ps:或者循环结束时返回,刚开始不知道这个函数结束条件可以没有return，只要函数中的语句全部执行完就可以返回，明白这点通过模拟代码过程就可以想明白了)，同时将该位置的使用数字恢复未使用的状态，即回溯操作 （由于path[]在循环刚开始时会被覆盖，因此不必恢复path
的状态）
(2)代码实现思路：
递归函数dfs，设置两个数组，path记录每一个位置存储的数字，st记录哪一个数字被使用过，当path的长度到达3时，输出并返回；否则依次利用st将未使用过的数字存入path数组中，同时将正在使用的st标志出来，然后递归下一个位置，再回溯到原来的状态，即令当前循环的st[i]恢复未使用的状态。最终递归第1个位置，即0。
(3)代码实现：
#include <iostream>
using namespace std;
const int N=7;
int path[N];
bool st[N];
int n;
void dfs(int u)
{
if(u==n)
{
for(int i=0;i<n;i++) cout<<path[i]<<" ";
cout<<endl;
return ;
}
for(int i=1;i<=n;i++)
{
if(!st[i])
{
path[u]=i;
st[i]=true;
dfs(u+1);
st[i]=false;
}
}
//return ;
}
int main() {
cin>>n;
dfs(0);
return 0;
}
2.AcWing 843.n-皇后问题
方法一
(1)算法思想：
利用上题的思路，通过dfs函数中的条件判断，不仅实现了回溯操作，还进行了剪枝操作（即发现条件不符合时直接跳过这种情形，而不是把这种情况完成再进行排除，从而减少了时间复杂度），这里的条件判断要对行，列，对角线，反对角线进行，由于每一行都有且只有一个皇后，因此可以将上题的path数组的位置看作行，每一个位置上的数字看成列号，通过函数关系，表达出对角线和反对角线的由行号和列号表达的恒等式，进而实现条件判断。当条件判断成立时，便存入皇后，同时递归下一个位置（这里可以通过模拟代码过程来让思路更清晰一些），最后要恢复现场。
(2)代码实现思路：
设置三个数组col[],de[],ude[]分别表示列，对角线，反对角线的占用情况,本题通过行号和列号即可实现条件判断，行号由位置序号实现，列号通过循环的i实现，当到达最后一行时，即dfs(u)的u到达n时，就可以返回整个g[N][N]数组，同时结束循环。否则循环判断哪一个列号处于该列，该对角线，该反对角线未被占用的状态，这里对角线和反对角线的表达式可以将行号看成y,列号看成x，所以主对角线是y=-x，同时又有一些对角线有斜距，因此对角线的方程可以总体写为y=-x+b，所以同一对角线的b是相同的，所以恒等式为b=x+y，当b不同时，则代表该对角线未被占用；同理，反对角线的方程是y=x+b,所以恒等式为b=y-x，又可能存在负数的情况，所以对方程两边同时加上N，不改变恒等式的性质，所以恒等式最终为b+N=y-x+N。因此条件判断为col[i],de[x+y],ude[y-x+N]都未被占用时，将该位置设为皇后，同时将该位置标记为已占用，再递归下一行，再回复现场，即将该位置标记为未占用，并且将皇后恢复初始态。
(3)代码实现：
#include <iostream>
using namespace std;
const int N=20;
char g[N][N];
bool col[N],de[N],ude[N];
int n;
void dfs(int u)
{
if(u==n)
{
for(int i=0;i<n;i++) puts(g[i]);
cout<<endl;
return ;
}
for(int i=0;i<n;i++)
{
if(!col[i]&&!de[u+i]&&!ude[u-i+n])
{
g[u][i]='Q';
col[i]=de[u+i]=ude[u-i+n]=true;
dfs(u+1);
col[i]=de[u+i]=ude[u-i+n]=false;
g[u][i]='.';
}
}
}
int main() {
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
g[i][j]='.';
dfs(0);
return 0;
}方法二
(1)算法思想：
将函数的参数设置为更易于理解的三个参数，即行号，列号，皇后数量，将整个过程看成从第一格向右行走，当走出格子，即当列号到最后时，走到下一行第一列，当行号到最后且皇后数充满后，输出并返回函数。递归到下一个状态，有两种状态，若不放皇后，则增加列号，若放皇后，则增加列号和皇后。
(2)代码实现思路：
见上
(3)代码实现：
#include <iostream>
using namespace std;
const int N=20;
char g[N][N];
bool row[N],col[N],de[N],ude[N];
int n;
void dfs(int x,int y,int s)
{
if(y==n) y=0,x++;
if(x==n)
{
if(s==n) {
for (int i = 0; i < n; i++) puts(g[i]);
cout << endl;
}
return ;
}
if(!row[x]&&!col[y]&&!de[x+y]&&!ude[n+x-y])
{
g[x][y]='Q';
row[x]=col[y]=de[x+y]=ude[n+x-y]=true;
dfs(x,y+1,s+1);
row[x]=col[y]=de[x+y]=ude[n+x-y]= false;
g[x][y]='.';
}
dfs(x,y+1,s);
}
int main() {
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
g[i][j]='.';
dfs(0,0,0);
return 0;
}(二).BFS
简介：一般通过队列实现，当边的权值相同时具有最短性，可以求最少操作步数。
1.迷宫问题 (AcWing 844.走迷宫)
(1)算法思想：
先设置存储地图信息的数组g[][]，存储当前点位到起点的距离数组d[][]，存储位置的队列q，设置寻找四个方向的数组减少条件判断语句，队列中存储的位置都是到达的点位，取出队头，再寻找它四个方向哪个方向可以前进(bfs的体现)，若可以前进则将距离加1，同时入队。最后返回地图右下角的点的d[][]数组的值
(2)代码实现思路：
初始化数组g[][],即输入的信息，d[][]，即将每一个位置赋值为-1，同时为d[0][0]即起点赋值为0，设置寻找周围四个方向的数组，即dx={-1,0,1,0},dy={0,1,0,-1};队列中的元素都是已经走过的元素，初始为起点，将队头取出，判断队头四个方向是否溢出，无障碍，未走过。若满足条件，则入队，同时将该点的距离加1，最后输出右下角的点的距离，即d[m][n].
(3)代码实现：
#include <iostream>
#include <cstring>
using namespace std;
const int N=110;
typedef pair<int,int> PII;
int g[N][N],d[N][N];
PII q[N*N];
int m,n;
int bfs()
{
memset(d,-1,sizeof d);
d[0][0]=0;
q[0]={0,0};
int hh=0,tt=0;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
while(hh<=tt)
{
auto t=q[hh++];
for(int i=0;i<4;i++)
{
int x,y;
x=t.first+dx[i],y=t.second+dy[i];
if(x>=0&&y>=0&&x<n&&y<m&&g[x][y]==0&&d[x][y]==-1)
{
d[x][y]=d[t.first][t.second]+1;
q[++tt]={x,y};
}
}
}
return d[n-1][m-1];
}
int main() {
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>g[i][j];
cout<<bfs();
return 0;
}
2.AcWing 845. 八数码
(1)算法思想：
将三维矩阵状态用一个字符串来表示，用哈希表映射当前状态需要的操作次数。
dfs函数:先记录终点的状态，将初始状态的字符串加入队列当中，再设置偏移量数组，当队列不空时执行循环，先出队头，记录队头状态的操作次数，将当前x在字符串中的位置计算出在三维矩阵中的位置，判断下一步朝哪个方向移动合法，这里的移动指的是在该状态字符串中交换x与下一个位置，如果当前交换后的状态之前未被哈希表存储过（即之前没有到达过该状态），就将该状态的操作次数置为上一个状态加1，再将该状态加入到队尾，最后恢复之前未交换的状态（即再交换一次）。
(2)代码实现思路：
先用一个string类型的字符串读入初始状态。
dfs函数:记录终点状态的字符串表示，设置一个记录每一个状态字符串的队列q,设置一个记录字符串状态对应的操作次数的哈希表d。将初始状态的字符串加入队列当中，初始化初始状态的操作次数为0，即d[start]=0，再设置偏移量数组。当队列不为空时执行循环，首先取出队头赋值给t，再出队，记录队头对应的操作次数distance，如果队头等于终点状态就返回此时的distance。将x在当前状态的字符串的位置赋值给k,用k计算出x在三维矩阵中的位置，即x=k/3,y=k%3。枚举四个方向，用a,b记录下一个位置，如果下一个位置合法就在字符串当中交换下一个位置和当前x的位置。再检查新的状态是否被记录过，如果没有被记录过就将新状态的操作数设置为上一个状态的操作数加1，即distance+1，再将新状态入队，最后恢复状态，即再次交换x的位置与下一个位置。
(3)代码实现：
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <unordered_map>
using namespace std;
int bfs(string start)
{
string end="12345678x";
queue<string> q;
unordered_map<string,int >d;
d[start]=0;
q.push(start);
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
while(q.size())
{
auto t=q.front();
q.pop();
int distance=d[t];
if(t==end) return distance;
int k=t.find('x');
int x=k/3,y=k%3;
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a>=0&&b>=0&&a<3&&b<3)
{
swap(t[k],t[3*a+b]);
if(!d.count(t))
{
d[t]=distance+1;
q.push(t);
}
swap(t[k],t[3*a+b]);
}
}
}
return -1;
}
int main()
{
string start;
for(int i=0;i<9;i++)
{
char c;
cin>>c;
start+=c;
}
cout<<bfs(start);
return 0;
}(三).有向图
简介：实现有向图，再通过设置两点之间相互指向就实现了无向图，而树是一种特殊的图，即无环连通图，因此实现有向图就可以解决绝大多数问题，一般有邻接矩阵和邻接表两种实现方式，常用邻接表（与哈希类似）
1.dfs遍历树 (AcWing 846.树的重心)
(1)算法思想：
dfs可以计算每一个子树的结点个数
首先像哈希表一样设置头指针数组h[]，以及链表的相关变量，一个存储每个节点是否被访问过的数组st[]，以及一个存储最终答案的变量ans。删除一个节点剩余各块的节点个数res，以及包该节点的子树的节点个数sum。由于本题是树，所以是创建时要建立双向的边，添加操作与哈希表插入完全类似。
dfs函数，函数返回包含该节点的子树节点个数，寻找未遍历过的子节点，通过递归的方式计算子树中结点最大的数目即为res，通过累加每一个子树的节点个数，计算sum，再比较除去该节点的所有子树（包含该节点）的结点数目与res的最大值，同时比较此时的最终答案ans和res大小。
(2)代码实现思路：
存在一条连接a,b的边，即将a,b互相指向。通过add函数实现a指向b。初始化每一个头指针为-1。
add函数：首先将待插入节点的值赋值为b，即e[idx]=b,该节点的下一个节点指向头指针指向的节点，即ne[idx]=h[a]，最后将头指针指向下一个节点,即h[a]=idx++
dfs函数：首先将该点标记为已经访问，初始化包含该节点的子树的节点个数sum为1，删除该节点节点剩余各块的节点个数res为0，循环遍历该节点的每一个子节点，寻找未访问过的子节点，再递归该子节点获得它的sum，res为最大的连通子图节点数，即选取res与该节点子树的节点数目的最大值，再将该节点的sum加上子节点的sum，即为该部分的节点个数，最后计算不包含该部分的节点个数，即将总的节点个数减去sum，选取它和res中较大的一个，最终的结果为所有res较小的一个，即ans。
(3)代码实现：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e5+10;
bool st[N];
int h[2*N],e[2*N],ne[2*N],idx;
int n;
int ans=N;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u)
{
st[u]= true;
int sum=1;
int res=0;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j])
{
int s=dfs(j);
res=max(res,s);
sum+=s;
}
}
res=max(res,n-sum);
ans=min(ans,res);
return sum;
}
int main() {
cin>>n;
memset(h,-1,sizeof h);
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
add(a,b),add(b,a);
}
dfs(1);
cout<<ans;
return 0;
}
2.bfs遍历树 (AcWing 847.图中点的层次)
(1)算法思想：
如上题操作创建一个树
bfs函数，创建一个距离数组d[],即该点距离节点1的距离，用数组模拟队列，将队头弹出，将未遍历过的子节点入队，同时修改该子节点到节点1的距离，最终返回最后一个节点到结点1的距离。
(2)代码实现思路：
bfs函数：初始化队列，将节点1入队，初始化距离数组，并将节点1的距离设为0。将队头出队，遍历队头的子节点，若未遍历过则将他的距离等于父节点的距离加1，同时入队，函数返回第n个点的距离。
(3)代码实现：
#include <iostream>
#include <cstring>
using namespace std;
const int N=1e5+10;
int q[N],d[N],h[2*N],e[2*N],ne[2*N],idx;
int n,m;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{
int hh=0,tt=0;
q[0]=1;
memset(d,-1,sizeof d);
d[1]=0;
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(d[j]==-1)
{
d[j]=d[t]+1;
q[++tt]=j;
}
}
}
return d[n];
}
int main() {
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b;
cin>>a>>b;
add(a,b),add(b,a);
}
cout<<bfs();
return 0;
}
(四).拓扑序列
简介：一个有向无环图必存在拓扑序，入度为0的点一定在当前状态的图中是最靠前的节点，因此每次输出入度为0的点就是拓扑序
1.AcWing 848.有向图的拓扑序列
(1)算法思想：
由于入度为0的点一定是当前图的最前面的点，因此类似宽度优先遍历，不过将每个入度为0的点出队时，要进行子节点的入度个数减1，同时判断子节点是否产生出入度为0的点，将其加入队列当中，如果进入队列的个数是全部节点，就说明存在拓扑序列，同时队列中的出队顺序就是拓扑序列。
(2)代码实现思路：
存在一条连接a,b的边，即将a,b互相指向。通过add函数实现a指向b，同时将b节点的入度加1。初始化每一个头指针为-1。
初始化加入a指向b的边的时候add函数再将b节点的入度加1，即d[b]++
top_sort函数：先初始化队头队尾，再循环遍历每一个节点，寻找入度为0的点，并将其加入队列中。取出队头，并将被其指向的节点的入度数目减1，如果此时又产生了入度为0的点，则将其加入队列当中，整个过程类似于bfs，若最后全部节点都进入队列当中，即tt=n-1，则将其输出
(3)代码实现：
#include <iostream>
#include <cstring>
using namespace std;
const int N=1e5+10;
int q[N],d[N],h[N],e[N],ne[N],idx;
int n,m;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool top_sort()
{
int hh=0,tt=-1;
for(int i=1;i<=n;i++)
if(!d[i]) q[++tt]=i;
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
d[j]--;
if(!d[j]) q[++tt]=j;
}
}
return tt==n-1;
}
int main() {
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b;
cin>>a>>b;
add(a,b),d[b]++;
}
if(top_sort())
{
for(int i=0;i<n;i++) cout<<q[i]<<" ";
puts("");
}
else
cout<<-1;
return 0;
}
(五).最短路算法
1.朴素dijkstra (AcWing 849. Dijkstra求最短路 I)
(1)算法思想：
由于该图为稠密图，因此存储方式采用邻接矩阵，由于存在重边，因此在读入边的时候要取最小的边。
dijkstra函数：首先初始化距离矩阵dist为无穷，将起点初始化为1。寻找在所有未获得最短距离的点st[]中距离最小的点，这个点就是最小距离的点，将其加入st[]中。再遍历加入该点之后个点的距离是否变小，若变小则更新（即判断该点到子节点的权值加上该点的距离是否比子节点的距离小）。最后输出第n个节点的距离。
(2)代码实现思路：
首先初始化邻接矩阵，将每个边设为无穷，再输入每个边的权值，考虑重边，因此若有两条节点相同的边，取最小的权值。
dijkstra函数：将每个点到起点的距离矩阵dist[]初始化为无穷，并将起点的距离设为0。下面遍历n个节点，获得每个节点的距离矩阵，在每次遍历中，先设置一个记录最小距离的节点t，遍历n个节点，寻找未获得最小距离的点，即st[j]=false，同时在这些点中距离最小。之后将其置为已找到st[t]=true。再根据该点，遍历n个节点，寻找是否存在某个点的最小距离因为该点最小距离的确定而发生变化，即min(dist[j], dist[t] + g[t][j])。最后输出第n个节点的距离。
(3)代码实现：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=510;
int g[N][N],dist[N];
int n,m;
bool st[N];
int dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=1;i<=n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j]&&(t==-1||dist[t]>dist[j]))
{
t=j;
}
}
st[t]=true;
for(int j=1;j<=n;j++)
{
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
}
if(dist[n]==0x3f3f3f3f) return -1;
else return dist[n];
}
int main() {
cin>>n>>m;
memset(g,0x3f,sizeof g);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
}
cout<<dijkstra();
return 0;
}
2.堆优化dijkstra (AcWing 850. Dijkstra求最短路 II)
(1)算法思想：
该图为稀疏图，因此存储时采用邻接表存储，同时要对每一条边加上权重属性。
dijkstra函数：首先初始化距离矩阵dist为无穷，将起点初始化为1。设置一个小顶堆，初始时加入起点，队列中每个元素包含距离和节点序号两个属性。当前距离起点最小的点即为堆顶，取出堆顶，标记该元素已找到最小距离。再遍历加入该点之后他的子节点距离是否变小，若变小则将其加入堆中同时更新距离。最后输出第n个节点的距离。
(2)代码实现思路：
首先初始化邻接表，记录每个边的属性（不需要像上题一样选择最小的边，因为该算法中小顶堆默认选择最小的边）
dijkstra函数：将每个点到起点的距离矩阵dist[]初始化为无穷，并将起点的距离设为0。建立一个小顶堆，每个元素包含距离，节点序号两个属性，初始将起点加入其中。再弹出堆顶，该元素即为当前可确认的距离起点最小的节点，将其置为已找到st[t]=true。再根据该点，遍历他的节点，寻找是否存在某个点的最小距离因为该点最小距离的确定而发生变化，如果存在更新该子节点的距离矩阵，同时将该点加入堆中。最后输出第n个节点的距离。
(3)代码实现：
//堆优化
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N=10010;
int dist[N],e[N],idx,ne[N],w[N],h[N];
int n,m;
bool st[N];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,1});
while(heap.size())
{
auto t=heap.top();
heap.pop();
int ver=t.second,distance=t.first;
if(st[ver]) continue;
st[ver]=true;
for(int i=h[ver];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[ver]+w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;
else return dist[n];
}
int main() {
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
cout<<dijkstra();
return 0;
}3.Bellman-Ford算法 (AcWing 853. 有边数限制的最短路)
(1)算法思想：
定义一个边的结构体，包含两个点以及边的权值
bellman-ford函数：初始化距离数组，接着遍历k次，在每次遍历中，寻找加入某点后他的子节点点距离是否变小，若变小则更新，即判断该点到子节点点的权值加上该点的距离是否比子节点的距离小。注意该距离更新时可能会导致参与的边的数量大于k，因此应在每次遍历前设置一个备份数组，记录在k次遍历中，本次遍历的上一次的距离数组状态，在该次遍历中对每条边的距离数组更新时采用备份数组，确保本次更新范围在当前的边数限制内。返回dist[N]，当该值足够大时即说明未找到（因为负边会使无穷减小）
(2)代码实现思路：
创建关于边的结构体，包含一个边的两端节点和边的权值。
bellman-ford函数：初始化距离数组为无穷，由于有限的边，因此将本次遍历所使用的距离数组都使用备用数组，即backup[]=dist[上一次]，通过这个备用数组更新每个节点的距离数组。
(3)代码实现：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=510,M=10010;
int dist[N],backup[N];
struct Edge{
int a,b,w;
}edge[M];
int n,m,k;
int bellman_ford()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<k;i++)
{
memcpy(backup,dist,sizeof dist);
for(int j=0;j<m;j++)//若没有备份数组可能会出现更新m次边，即所有节点连成一串
{
int a=edge[j].a,b=edge[j].b,w=edge[j].w;
dist[b]=min(dist[b],backup[a]+w);
}
}
if(dist[n]>0x3f3f3f3f/2) return -1;
return dist[n];
}
int main() {
cin>>n>>m>>k;
for(int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w;
edge[i]={a,b,w};
}
int t=bellman_ford();
if(t==-1) cout<<"impossible";
else cout<<t;
return 0;
}
4.SPFA算法 (AcWing 851. spfa求最短路)
(1)算法思想：
由于bellman_ford算法中每次遍历时距离数组不一定发生变化，只有当上一个节点的距离数组改变时，该节点的距离数组才发生变化（只有我变小了，我后面的点才会变小）。因此可以通过一个队列来进行优化。
该算法与堆优化版的dijkstra算法类似，设置一个队列来存储待更新的点，初始将起点入队，同时标记该点在队列中，然后在每次遍历中，弹出队头，同时将该点取消标记，在判断该点的子节点距离是否变小，若变小且不在队列中，则入队同时标记为已入队。
(2)代码实现思路：
同上。
(3)代码实现：
//堆优化
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=10010;
int dist[N],e[N],idx,ne[N],w[N],h[N];
int n,m;
bool st[N];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
queue<int> q;
q.push(1);
st[1]= true;
while(q.size())
{
auto t=q.front();
q.pop();
st[t]=false;//与dijkstra算法不同之处
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];
if(!st[j])
{
st[j]=true;
q.push(j);
}
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}
int main() {
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
int t=spfa();
if(t==-1) cout<<"impossible";
else cout<<t;
return 0;
}5.SPFA算法判断负环 (AcWing 852. spfa判断负环)
(1)算法思想：
设置一个记录边数的数组cnt[],在每次更新边后，将该点的cnt数组加1，该数组的值大于n,则说明存在负环。由于判断的不是从起点开始存在负环，而是全部图中是否存在负环，因此初始要将所有点都放入队列当中。
(2)代码实现思路：
同上。
(3)代码实现：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=10010;
int dist[N],e[N],idx,ne[N],w[N],h[N],cnt[N];
int n,m;
bool st[N];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool spfa()
{
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]++;
if(cnt[j]>=n) return true;
if(!st[j])
{
st[j]=true;
q.push(j);
}
}
}
}
return false;
}
int main() {
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
int t=spfa();
if(spfa()) cout<<"Yes";
else cout<<"No";
return 0;
}6.Floyd算法 (AcWing 854. Floyd求最短路)
(1)算法思想：
初始化距离数组，将自己指向自己的点的距离初始化为0，其余初始化为无穷。同时由于存在重边，因此在读入时要选取最小的权值的边。
floyd函数：该函数包含三层循环，每次遍历k个点，更新两点距离取该两点距离和加入其他的两点距离的最小值
(2)代码实现思路：
同上。
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=210,INF=1e9;
int d[N][N];
int n,m,Q;
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]);
}
int main() {
cin>>n>>m>>Q;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(j==i) d[i][j]=0;
else d[i][j]=INF;
}
while(m--)
{
int a,b,w;
cin>>a>>b>>w;
d[a][b]=min(d[a][b],w);
}
floyd();
while(Q--)
{
int a,b;
cin>>a>>b;
if(d[a][b]>INF/2) cout<<"impossible"<<endl;
else cout<<d[a][b];
}
return 0;
}
(六).最小生成树
1.朴素Prim算法 (AcWing 858. Prim算法求最小生成树)
(1)算法思想：
与朴素dijkstra思想几乎一样，只不过Prim算法的距离指的是点到最小生成树的集合的距离，而dijkstra算法的距离是点到起点的距离。同时要注意本题由于未设起点所以要迭代n次，并且图中存在负的自环，因此在要在更新距离之前修改最小生成树的总距离。
(2)代码实现思路：
该图为稠密图，因此用邻接矩阵来存储，同样将每条边初始化无穷，由于为无向图，所以要将边的信息记录两次，同时保证为最小值。
prim函数：初始化距离数组dist[],迭代n次，每次寻找不在集合且距离最小的点（若为第一次迭代则直接加入第一个点），之后先修改总距离，再更新加入该点之后，其他每个点到集合的距离（注意，这里与dist进行比较的是初始两点之间的边的数据，而不是dist加上初始边），最后将该点加入集合。
(3)代码实现：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=10010,INF=0x3f3f3f3f;
int g[N][N],dist[N];
bool st[N];
int n,m;
int prim()
{
memset(dist,0x3f,sizeof dist);
int res=0;
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1)||dist[t]>dist[j])
t=j;
if(i && dist[t]==INF) return INF;
if(i) res+=dist[t];
for(int j=1;j<=n;j++)
{
dist[j]=min(dist[j],g[t][j]);
}
st[t]=true;
}
return res;
}
int main() {
cin>>n>>m;
memset(g,0x3f,sizeof g);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
int t=prim();
if(t==INF) puts("impossible");
else cout<<t;
return 0;
}
2.Kruskal算法(稀疏图) (AcWing 859. Kruskal算法求最小生成树)
(1)算法思想：
将所有边按照权重大小排序，再从小到大枚举每一条边，运用并查集查看两点之间的边是否在集合中，若该边不在集合内，则加入集合中。
(2)代码实现思路：
首先利用结构体记录每条边的属性，即两个端点和权值。排序每一条边，初始化并查集（上面有），遍历每一条边，寻找两个端点的祖先，若该边的两个端点有共同的祖先，则说明在该边在集合内，否则将两个点合并进同一个集合，再修改总距离，同时将集合内点的数量加1。
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=200010;
struct Edge{
int a,b,w;
bool operator <(const Edge &W)const {
return w < W.w;
}
}edges[N];
int n,m;
int p[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main() {
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w;
edges[i]={a,b,w};
}
sort(edges,edges+m);
for(int i=1;i<=n;i++) p[i]=i;
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)
{
p[a]=b;
res+=w;
cnt++;
}
}
if(cnt<n-1) puts("impossible");
else cout<<res;
return 0;
}
(七).二分图
简介：使所有点划分为两个集合，集合之间没有边，因此一个图为二分图的充要条件为图中不存在奇数环（奇数个点）。
1.染色法 (AcWing 860. 染色法判定二分图)
(1)算法思想：
该图通过邻接表方式存储，将每一个边的两个端点通过bfs染成不同的颜色，即通过一个点遍历他的所有邻接点，将它们染成其他颜色。
(2)代码实现思路：
初始化邻接表，输入每条边的信息，由于为无向图，所以一条边要添加两次，之后设置一个判断变量flag初始为true，再遍历n个节点，首先判断该点是否已经染色，若未染色，则将其染色为1，同时递归他的节点，若递归的结果返回为false（即if(!dfs[i,1]）则将flag改为false同时结束循环。
dfs函数：先将该点染色，然后遍历他的邻接点：1 若未染色，则将其染色为其他颜色（3-c[i]，ps:颜色为1或2，通过3-c实现颜色相反），与上面的操作相同，都是利用递归实现染色加判断，若返回false，则将该点的递归结果返回false；2 若他的邻接点的颜色与他相同，同样返回false
(3)代码实现：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010;
int h[N],ne[N],e[N],idx;
int color[N];
int n,m;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool dfs(int a,int c)
{
color[a]=c;
for(int i=h[a];i!=-1;i=ne[i])
{
int j=e[i];
if(!color[j])
{
if(!dfs(j,3-c)) return false;
}
else if(color[j]==color[a]) return false;
}
return true;
}
int main() {
memset(h,-1, sizeof h);
cin>>n>>m;
while(m--)
{
int a,b;
cin>>a>>b;
add(a,b),add(b,a);
}
bool flag=true;
for(int i=1;i<=n;i++)
{
if(!color[i])
if(!dfs(i,1))
{
flag=false;
break;
}
}
if(flag) puts("Yes");
else puts("No");
return 0;
}
2.匈牙利算法 (AcWing 861. 二分图的最大匹配)
(1)算法思想：
两个集合中都存在一些点，以左集合出发，查找两个集合之中匹配成功的点的个数。如果左集合的某一个点发现与自己相连的节点已经被占有，则查询占有该节点的左集合的点是否有其他可配对的点，若有则两全其美，否则继续寻找，若仍未找到，则配对失败。
(2)代码实现思路：
用邻接表存储，设置一个配对数组match[]（match[a]=b表示左集合节点b是与右集合节点a匹配），判重数组st[]，表示右节点是否被匹配。
遍历左集合的全部节点，首先将右节点全部设为未匹配，若能成功配对，则将配对成功总个数加1。
find函数，遍历与该节点相连的右集合点j（题目规定相连的点必为异侧集合），若j未匹配，则将其设为匹配（第一次进入函数该条件无用，因为每个点都已经设为未匹配；该条件控制后面的find函数，即与该右节点已经匹配的左节点在下一次遍历邻接点时跳过该右节点），如果右节点还未匹配(创建该数组时默认初始化为0)或者与该右节点匹配的左节点能够找到其他节点，则将该右节点匹配为该左节点，同时返回true。
(3)代码实现：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=510,M=100010;
int h[N],e[M],ne[M],idx;
int n1,n2,m;
int match[N];
bool st[N];
void add(int a,int b)
{
e[idx]=a,ne[idx]=h[a],h[a]=idx++;
}
bool find(int x)
{
for(int i=h[x];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j])
{
st[j]=true;
if(match[j]==0||find(match[j]))
{
match[j]=x;
return true;
}
}
}
return false;
}
int main() {
cin>>n1>>n2>>m;
while(m--)
{
int a,b;
cin>>a>>b;
add(a,b);
}
int cnt=0;
for(int i=1;i<=n1;i++)
{
memset(st,false,sizeof st);//每次枚举将右侧节点都设为未匹配
if(find(i)) cnt++;
}
cout<<cnt;
return 0;
}