注意点
1. 若有多组数据的话,记得每次都要初始化图
fill(h,h+N,0);
最短路径
比较:SPFA v.s dijkstr
1.st数组的含义不同:
1) spfa中st指该点是否在队列中
2) dijkstra中指该点是否已更新完毕(打勾)
SPFA
- 除了路径计数cnt类的问题不能用,其他更新最大最小以及路径问题pre都可以用
- 可以判断负环
1) spfa求最短路径
bool st[N];
//是否在队列中
int dis[N];
//最短距离
void spfa(int s){
fill(dis,dis+N,INF);
queue<int>q;
dis[s]=0;
q.push(s);
st[s]=1;
while(q.size()){
auto t=q.front();
q.pop();
st[t]=0;
//遍历它的所有边
for(int i=h[t];i;i=ne[i]){
auto j=e[i];
if(dis[j]>dis[t]+w[i]){
//如果距离可以缩短
dis[j]=dis[t]+w[i];
if(st[j]==1) continue;
//已经在队列中就不用加入
st[j]=1;
q.push(j);
}
}
}
}
2) spfa判断负环
负环的判断依据:如果到达某个点的最短路径所经过的顶点>=n+1
,则存在负环,因为这比该图的所有顶点数还多
做法:
1. 先添加一个超级源点,并可以到达图中所有的顶点,且距离为0( 此时该图共有n+1个点 )
2. 然后求该超级源点到图中各个点的最短距离中,并同时保存到达每个顶点的最短距离所经过的顶点数cnt
3. 若某一时刻,该顶点数cnt>=n+2
( 比图中的所有顶点还多 ),则存在负环
bool st[N];
//有没有在队列中
int dis[N];
//超级源点到达每个点的最短距离
int cnt[N];
//到达每个点的最短距离的路径上的顶点数
bool spfa(int s){
fill(dis,dis+N,INF);
queue<int>q;
dis[s]=0;
q.push(s);
st[s]=1;
//该最短路径上仅一个点
cnt[s]=1;
while(q.size()){
auto t=q.front();
q.pop();
st[t]=0;
for(int i=h[t];i;i=ne[i]){
auto j=e[i];
if(dis[j]>dis[t]+w[i]){
dis[j]=dis[t]+w[i];
//更新经过的路径上的顶点数
cnt[j]=cnt[t]+1;
if(cnt[j]>=n+2){
//点还比图上的所有点数多了,则存在负环
//算入超级源点后,图中共有n+1个点,则大于等于n+2才可判断有负环
return true;
}
if(st[j]!=1){
st[j]=1;
q.push(j);
}
}
}
}
return false;
//能全部执行完毕,不存在负环,否则会无限循环下去
}
int main(){
//建立一个超级源点0,可以到达图中所有的点,且距离为0
for(int i=1;i<=n;i++){
add(0,i,0);
}
spfa(0);
}
Dijkstra
- 可用于路径计数,也可以求最大点权和
- Dijkstra一般在距离小于时更新那里修改
//pair三件套
using pair<int,int>;
#define x first
#define y second
int dis[N];//最短距离数组
bool st[N];//访问数组
void dijkstra(int s){
priority_queue<PII,vector<PII>,greater<PII>> pq;
//小根堆,dijkstra使用2维度,一维是dis,二维是结点编号
//greater是小的在前面
fill(dis,dis+N,INF);
//距离置为无穷大
dis[s]=0;//起点距离置为0
pq.push({0,s});
while(pq.size()){
auto t=pq.top();//1. 选点
pq.pop();
st[t.y]=1;//设置头节点已访问 2. 打勾
for(int i=h[t.y];i;i=ne[i]){//3. 加边
auto j=e[i];
if(st[j]==1) continue;//不更新打过勾的点(已更新完毕的点)
//访问过,则排除
if(dis[j]>dis[t.y]+w[i]){//4. 更新
//可更新距离
dis[j]=dis[t.y]+w[i];
pq.push({dis[j],j});
}
}
}
}
Floyd
- 可求全源最短路径
- 距离数组即为图数组(g[i][j]表示i到j的最短距离)
- 最后判断i与j之间是否有路劲,可
g[i][j]>=INF/2
(INF一般取1e9
) - 使用floyd算法一般采用邻接矩阵,而且邻接矩阵对于重边,每次只保存权重最小的边
int g[N][N];//全源最短路径floyd一般用邻接矩阵
void floyd(){
for(int k=1;k<=n;k++){
//以k为中转点
for(int i=1;i<=n;i++){
//i为起点
for(int j=1;j<=n;j++){
//j为终点
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
}
}
}
int main(){
fill(g[0],g[0]+N*N,INF);
for(int i=1;i<=n;i++){
g[i][i]=0;//自己到自己的最短距离是0
}
while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
//邻接矩阵每次取权值最小的边
}
floyd();
if(g[a][b]>=INF/2){
cout<<"impossible"<<endl;
}else{
cout<<g[a][b]<<endl;
}
}
最小生成树
定义:找一个树能够连接图的所有顶点,且权值之和最小
使用Kruscal算法:
1. 定义并查集(使用并查集一定要记得初始化fa[i]=i
)
2. 对所有边按权值从小到大排序
3. 枚举所有的边,若该边的两个顶点不属于同一个集合,则合并这两个集合,并且权值和加上该边的权值
4. 用一个cnt
记录该集合有多少个顶点,若最终结果不为n
,则不存在最小生成树
5. 不需要考虑重边
int f[N];//并查集
void init(){
for(int i=1;i<=n;i++) f[i]=i;
}
int find(int x){
if(f[x]!=x) f[x]=find(f[x]);
return f[x];//注意:要fx
}
struct edge{
int a,b,w;
}edges[N];
bool cmp(edge a,edge b){
return a.w<b.w;
}
sort(edges,edges+m,cmp);
//将所有的边按照权值从小到大排序
int res=0;
//最小生成树的权值和
int cnt=1;
//最小生成树所含的顶点个数
for(int i=0;i<m;i++){
int a=edges[i].a,b=edges[i].b,w=edges[i].w;
int fa=find(a);
int fb=find(b);
if(fa!=fb){
//两个顶点是否是属于同一个集合
f[fa]=fb;
//合并集合
cnt++;
res+=w;
//更新最小生成树的属性
}
}
if(cnt==n){
cout<<res;
}else{//该最小生成树的顶点数不等于该图的顶点数,则该图不存在最小生成树
cout<<"impossible";
}
哈密顿回路
指的能否一笔连完整个图中的所有点,且除了起点和终点外,每个点只经过一次,且起点=终点
解决问题3部曲:
- 该路径长度cnt==n+1
- 该路径的起点与终点相同path[0]==path[n-1]
- 该路径两点之间都有边:g[path[i]][path[i+1]]=1( 判断哈密顿回路采用邻接矩阵方便 )
int papth[N];//某条路径
bool st[N];//代表所有点是否被访问过
//n为该图的结点数,cnt为该路径path的长度
bool check(int cnt){
fill(st,st+N,0);
//哈密顿回路判断3步曲
if(cnt!=n+1) return 0;//点数一定为n+1
//起点与终点相等
if(path[0]!=path[cnt-1]) return 0;
for(int i=0;i<cnt-1;i++){
if(g[path[i]][path[i+1]]==0) return 0;//没有边
st[nodes[i+1]]=1;
}
for(int i=1;i<=n;i++){
if(st[i]==0) return 0;
}
return 1;
}
拓扑排序
思路:
1. 添加有向边时,令被指向的顶点的度数+1
2. 先找度数为0的顶点将其放入队列中,并置为已访问
3. 遍历队列中的顶点,将其相连的顶点的度数-1
4. 若某一顶点度数为0,且未被访问过,则入队
bool st[N];//该节点是否被访问过(输出)
int d[N];//每个点的入度数
vector<int> path;//保存路径
void toposort(){
queue<int>q;
for(int i=1;i<=n;i++){
if(d[i]==0){
q.push(i);
st[i]=1;
path.push_back(i);
}
}
while(q.size()){
auto t=q.front();
q.pop();
for(int i=h[t];i;i=ne[i]){
auto j=e[i];
d[j]--;
if(d[j]==0&&st[j]==0){
q.push(j);
st[j]=1;
path.push_back(j);
}
}
}
}
int main(){
while(m--){
int a,b;
cin>>a>>b;
add(a,b);//a->b
d[b]++;//b的入度+1
}
toposort();
for(int i=1;i<=n;i++){//若还有没访问过的顶点,则不存在拓扑排序
if(st[i]==0){
cout<<-1;
return 0;
}
}
for(auto &i:path){
cout<<i<<" ";
}
}