知识点图片来源于董晓算法
图的存储：链式前向星
const int N=1e3+10,M=2e3+10,mod=998244353,inf=0x3f3f3f3f;//1e5就超时
struct edge{
int to,w,nxt;
};
edge e[N];//实际存储容器
int head[N],tot;
int n,m;
void init(){
forr(i,0,M)e[i].nxt=0;
forr(i,0,N)head[i]=0;
tot=0;
}
void addedge(int u,int v,int w){//加点
e[++tot].to=v;//指向的点
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
void solve(){
cin>>n>>m;
forr(i,1,m){
int u,v,w;cin>>u>>v>>w;
addedge(u,v,w);
}
//遍历一个点的出边
int now=3;
for(int i=head[now];i;i=e[i].nxt){
cout<<e[i].to<<' '<<e[i].w<<endl;
}
}
单源最短路
Dijkstra
O(n2)模板
样例
输入
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出
0 2 4 3
const int N=1e4+10,mod=998244353,inf=pow(2,31)-1;//1e5就超时
struct edge
{
int v,w;
};
int n,m,st;
vector<edge>e[N];
int dis[N],vis[N];
void dij(int s){
forr(i,0,n)dis[i]=inf;//都初始化为inf 注意now初始为0 dis[0]=inf
dis[s]=0;
forr(i,1,n){
int now=0;
forr(j,1,n)//取出距离st最短的点
if(!vis[j]&&dis[j]<dis[now])now=j;
vis[now]=1;//拿出来
// cout<<now<<endl;
for(auto ed:e[now]){//用now做跳板更新相邻的边
int v=ed.v,w=ed.w;
if(dis[v]>dis[now]+w)dis[v]=dis[now]+w;
}
}
}
void solve(){
cin>>n>>m>>st;
forr(i,1,m){
int a,b,val;
cin>>a>>b>>val;
e[a].push_back({b,val});
}
dij(st);
forr(i,1,n)cout<<dis[i]<<' ';
}
只适用于正边权，不能用于负边权
O(n2)
n=1e3 m=1e6稠密图能过
n=1e6 m=1e6 T
O(mlogm)堆优化
const int N=1e5+10,mod=998244353,inf=pow(2,31)-1;//1e5就超时
struct edge
{
int v,w;
};
int n,m,st;
vector<edge>e[N];
int dis[N],vis[N];
priority_queue<pair<int,int>>q;//默认为大根堆
void dij(int s){
forr(i,0,n)dis[i]=inf;//都初始化为inf 注意now初始为0 dis[0]=inf
dis[s]=0;q.push(make_pair(0,s));
while (q.size())
{
auto t=q.top();q.pop();
int now=t.second;
if(vis[now])continue;//把之前插入优先队列的遍历过的点跳过
vis[now]=1;
for(auto ed:e[now]){//用now做跳板更新相邻的边 松弛操作
int v=ed.v,w=ed.w;
if(dis[v]>dis[now]+w){
dis[v]=dis[now]+w;
q.push(make_pair(-dis[v],v));//把更新过的点扔进堆里 d[v]越小 -d[v]越大 利用负号构建小根堆
}
}
}
}
void solve(){
cin>>n>>m>>st;
forr(i,1,m){
int a,b,val;
cin>>a>>b>>val;
e[a].push_back({b,val});
}
dij(st);
forr(i,1,n)cout<<dis[i]<<' ';
}
O(mlogm)
m=1e6可过
路径记录和输出
void dij(int s){
forr(i,0,n)dis[i]=inf;//都初始化为inf 注意now初始为0 dis[0]=inf
dis[s]=0;q.push(make_pair(0,s));
while (q.size())
{
auto t=q.top();q.pop();
int now=t.second;
if(vis[now])continue;//把之前插入优先队列的遍历过的点跳过
vis[now]=1;
for(auto ed:e[now]){//用now做跳板更新相邻的边 松弛操作
int v=ed.v,w=ed.w;
if(dis[v]>dis[now]+w){
dis[v]=dis[now]+w;
pre[v]=now;//记录前驱点
q.push(make_pair(-dis[v],v));//把更新过的点扔进堆里 d[v]越小 -d[v]越大 利用负号构建小根堆
}
}
}
}
//输出任意一点到st的最短路径
void dfs_path(int now){//dfs从末点遍历到st
if(now==st)return cout<<now<<endl,void();
dfs_path(pre[now]);
cout<<now<<endl;
}
Bellman-Ford O(nm)
可以用来判断负环
P3385
struct edge{int v,w;};
vector<edge>e[N];
int d[N];//距离
int n,m;
bool bellmanford(int s){
forr(i,1,n)d[i]=inf;
d[s]=0;
bool fg;//是否松弛
//O(nm)
forr(i,1,n){//更新n次 因为一个点可以多次更新，所以可判负环
fg=0;
forr(u,1,n){//以每一个点为跳板
if(d[u]==inf)continue;
for(auto ed:e[u]){//更新每条出边
int v=ed.v,w=ed.w;
if(d[v]>d[u]+w)d[v]=d[u]+w,fg=1;
}
}
if(!fg)break;
}
return fg;//第n轮仍为true则有环 因为负边权让d越来越小 必定有松弛操作
}
void solve(){
cin>>n>>m;
forr(i,1,n)e[i].clear();
forr(i,1,m){
int u,v,w;cin>>u>>v>>w;
e[u].push_back({v,w});
if(w>=0)e[v].push_back({u,w});
}
cout<<(bellmanford(1)?"YES":"NO")<<endl;
}
SPFA O(nm) queue维护
struct edge{int v,w;};
vector<edge>e[N];
int d[N],vis[N],cnt[N],pre[N];//距离
int n,m;
//O(nm)
bool spfa(int s){
memset(d,0x3f,sizeof d);
memset(cnt,0,sizeof cnt);
memset(vis,0,sizeof vis);
memset(pre,0,sizeof pre);
queue<int>q;
d[s]=0,vis[s]=1;
q.push(s);
while(q.size()){
int now=q.front();q.pop();
vis[now]=0;//出队 可反复进队出队
for(auto ed:e[now]){
int v=ed.v,w=ed.w;
if(d[v]>d[now]+w){
d[v]=d[now]+w;
cnt[v]=cnt[now]+1;
pre[v]=now;//记录前驱点
if(cnt[v]>=n)return true;//这条路上边数有重复点 就有负边
if(!vis[v])q.push(v),vis[v]=1;//v不在队内 就放进去
}
}
}
return false;
}
void dfs_path(int now,int s){
if(now==s){//递归到起点
cout<<now<<endl;
return;
}
dfs_path(pre[now],s);
cout<<now<<endl;
}
void solve(){
cin>>n>>m;
forr(i,1,n)e[i].clear();
forr(i,1,m){
int u,v,w;cin>>u>>v>>w;
e[u].push_back({v,w});
if(w>=0)e[v].push_back({u,w});
}
cout<<(spfa(1)?"YES":"NO")<<endl;
}
多源最短路
Floyd 动态规划思想 O(n3)
使用邻接矩阵
“插点”的思想
路径输出
Johnson 虚拟原点0 O(nmlogm)
一次SPFA，n次HD
P5905
const int N=3e3+10,M=6e3+10,mod=998244353,inf=1e9;
struct edge{int v,w;};
vector<edge>e[N];
int h[N],d[N],vis[N],cnt[N];
int n,m;
void spfa(int s){
forr(i,0,n)h[i]=inf;
memset(cnt,0,sizeof cnt);
memset(vis,0,sizeof vis);
queue<int>q;
h[s]=0,vis[s]=1;
q.push(s);
while(q.size()){
int now=q.front();q.pop();
vis[now]=0;//出队 可反复进队出队
for(auto ed:e[now]){
int v=ed.v,w=ed.w;
if(h[v]>h[now]+w){
h[v]=h[now]+w;
cnt[v]=cnt[now]+1;
if(cnt[v]>n){
cout<<"-1\n";
exit(0);
}
if(!vis[v])q.push(v),vis[v]=1;//v不在队内 就放进去
}
}
}
}
void dij(int s){
forr(i,0,n)d[i]=inf;//都初始化为inf 注意now初始为0 d[0]=inf
memset(vis,0,sizeof vis);
priority_queue<pair<int,int>>q;
d[s]=0;q.push(make_pair(0,s));
while (q.size())
{
auto t=q.top();q.pop();
int now=t.second;
if(vis[now])continue;//把之前插入优先队列的遍历过的点跳过
vis[now]=1;
for(auto ed:e[now]){//用now做跳板更新相邻的边 松弛操作
int v=ed.v,w=ed.w;
if(d[v]>d[now]+w){
d[v]=d[now]+w;
q.push(make_pair(-d[v],v));//把更新过的点扔进堆里 d[v]越小 -d[v]越大 利用负号构建小根堆
}
}
}
}
void solve(){
cin>>n>>m;
forr(i,1,m){
int u,v,w;cin>>u>>v>>w;
e[u].push_back({v,w});
}
forr(i,1,n){
e[0].push_back({i,0});
}
spfa(0);//h[i]是0到i点的最短路
forr(i,1,n){
for(auto &ed:e[i]){
ed.w+=h[i]-h[ed.v];//修改边权 加头去尾
}
}
forr(i,1,n){
dij(i);//以每个点为源跑dij d[j]是i到j的最短路
int ans=0;
forr(j,1,n){
if(d[j]==inf)ans+=j*inf;
else ans+=j*(d[j]+h[j]-h[i]);//还原权值
}
cout<<ans<<endl;
}
}
总结
