最短路
最短路问题相必大家都有接触，就是求一个图中的最短权重路径的和是多少
这种问题可以被抽象为很多种形式，算法的思维也很多，但归结到底都是最短路问题的探讨
先说最短路算法总共分为三种 dijkstra算法，spfa算法和foyd算法。
用的最多的是spfa算法 （主要是方便）
- 思维
1 将所有点全部变为正无穷（ inf ），并将起点存入队列
2 以起点为开始，用邻接表进行遍历，更新每个点（将每个点更新为距离最小的点）
3 直到找到最短路径
大多数的最短路问题都可以用spfa算法进行求解
int spfa(){
memset(dist,0x3f,sizeof dist); //第一步 将dist数组全变为正无穷
queue<int> q;
q.push(1); //将起点装进队列
dist[1]=0;
st[1]=true; //用布尔st 数组来判断是否点已在队列
while(q.size()){
int 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数组
dist[j]=dist[t]+w[i];
if(!st[j]){ //防止重复加入队列已有的点
st[j]=true;
q.push(j);
}
}
}
}
return dist[n]; //返回终点dist最小值
}
这里就不多讲了
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e6+10,M=5e6+10;
int h[N],rh[N],e[M],ne[M],idx;
int p[N],dmax[N],dmin[N];
bool st[N];
int n,m;
void add(int *h,int a,int b){
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void spfa_max(){
queue<int> q;
memset(st,0,sizeof st);
q.push(n);
dmax[n]=p[n];
while(q.size()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=rh[t];~i;i=ne[i]){
int j=e[i];
if(dmax[j]<max(p[j],dmax[t])){
dmax[j]=max(p[j],dmax[t]);
if(!st[j]){
st[j]=true;
q.push(j);
}
}
}
}
}
void spfa_min(){
queue<int> q;
memset(st,0,sizeof st);
memset(dmin,0x3f,sizeof dmin);
q.push(1);
dmin[1]=p[1];
while(q.size()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
if(dmin[j]>min(dmin[t],p[j])){
dmin[j]=min(dmin[t],p[j]);
if(!st[j]){
st[j]=true;
q.push(j);
}
}
}
}
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
memset(rh,-1,sizeof rh);
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
for(;m;m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(h,a,b),add(rh,b,a); //反向建边
if(c==2) add(h,b,a),add(rh,a,b);
}
spfa_max(); spfa_min(); //分别求起点路径最小权值的距离和终点路径权重到该点
int res=0;
for(int i=1;i<=n;i++) res=max(res,dmax[i]-dmin[i]);
cout<<res;
return 0;
}
这里来讲了下拓扑排序
拓扑排序
拓扑排序就是将图的每个点进行排序，以入度为0 为起点，进行沿着图进行排序输出
再讲拓扑排序之前，要讲两个概念入度和出度
-
啥是入度
就是一个点的有点多少个指向它的边（这里不能有重边） -
啥是出度
就是一个点有多少个它指向其他点的边（这里不能有重边）
拓扑排序的怎样写
1 记录入度和出度的多少
2 将入度为0的点装进队列
3 每次遍历点，将该点的入度减一，为0加入队列
其实具体问题还是要具体分析，但思维还是没什么差别
来一道具体问题
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=1e6+10;
int h[N],e[M],ne[M],idx; //邻接表
int d[N],r[N],c[N];
int n,m,ans;
inline int read() { //快读
char c = getchar(); int n = 0;
while (c < '0' || c > '9') { c = getchar(); }
while (c >= '0' && c <= '9') { n = (n << 1) + (n << 3) + (c & 15); c = getchar(); }
return n;
}
void add(int a,int b){ //存边
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void spfa(){
queue<int> q;
for(int i=1;i<=n;i++)
if(r[i]==0){
q.push(i); //入度为零，加入队列作为起点
d[i]=1;
}
while(q.size()){
int t=q.front();
q.pop();
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
d[j]+=d[t]; //记录此地以上有多少条食物链
r[j]--; //每次入度减一
if(!r[j]){ //为零加入队列
if(c[j]) q.push(j);
else ans+=d[j]; //出度为零为终点，此时加食物链的个数
}
}
}
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h); //邻接表初始化
for(;m;m--){
int a,b;
a=read(),b=read();
add(a,b); //食物链不存在重边
c[a]++; //入度和出度记录
r[b]++;
}
spfa();
cout<<ans; //输出
return 0;
}
最小生成树
这里我直接介绍最好用的 kruskal算法
- 原理
1 将所有权边由小到大排序（sort）
2 记录两点是否在一个集合（并查集）
3 累加权边
模板
struct Edge // 存储边
{
int a, b, w;
bool operator< (const Edge &W)const //重载
{
return w < W.w;
}
}edges[M];
int kruskal()
{
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) return 0x3f3f3f3f;
return res;
}
来一道简单题吧
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=110,M=1010;
int p[N];
int n,m;
struct ss{
int a,b,w;
bool operator <(const ss& W)const{
return w<W.w;
}
}s[M];
int find(int x){ //并查集找爸爸函数
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void kruskal(){
sort(s,s+m); //排序
for(int i=1;i<=n;i++) p[i]=i; //初始化并查集
for(int i=0;i<m;i++){
int a,b,w;
a=s[i].a,b=s[i].b,w=s[i].w;
int fx=find(a),fy=find(b);
if(fx!=fy){
p[fx]=fy;
cout<<a<<" "<<b<<endl; //输出连接的边
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
s[i]={a,b,w};
}
kruskal();
return 0;
}
好了我也才刚刚学完图论基础，也不是很懂，请见谅
