关于spfa
知识点
原始版 ---裸
应用：
一、判负环
两种方法
1.跑单源点bfs，如果某一个点入队了n-1次，存在
2.对于每个点dfs，如果此源点反被其他点更新，存在
证明：点i作为源点，d[i]==0 若i被更新，d[i]<0 定存在负环
优化：若初始d[]={0} 则最开始一定先跑权为负的边，更容易找到负环
int d[N]={0};fg=1;
for(int i=1;i<=n;i++){dfs(i);if(!fg)break;}
void dfs(int u){
if(!fg)return;
vis[u]=1;
for(int i=hd[u];i;i=e[i].next){
int v=e[i].v;
if(d[v]>d[u]+e[i].w){
if(vis[v]){fg=0;return;}
d[v]=d[u]+e[i].w;
dfs(v);
}
}
vis[u]=0;
}
二、网络流最小费用最大流
无限spfa直到没有可流的量
在原始spfa中，加入流量限制 ，记录入边
每次spfa结束后沿入边更新流量即可
queue<int>q;
bool spfa(int s,int t,int &flow,int &cost){
for(int i=1;i<=t;i++)d[i]=inf;
memset(vis,0,sizeof(vis));
memset(pre,-1,sizeof(pre));
q.push(s);vis[s]=1;a[s]=inf;
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=0;
for(int i=head[u];i!=-1;i=e[i].next){
int v=e[i].v;
if(e[i].cap>e[i].flow&&d[v]>d[u]+e[i].w){
d[v]=d[u]+e[i].w;
pre[v]=i;
a[v]=min(e[i].cap-e[i].flow,a[u]);
if(!vis[v]){
q.push(v);
vis[v]=1;
} }
}
}
if(d[t]==inf)return 0;
flow+=a[t];cost+=d[t]*a[t];
int u=t;
while(u!=s){
e[pre[u]].flow+=a[t];
e[pre[u]^1].flow-=a[t];
u=e[pre[u]].u;
}
return 1;
}
int flow=0,cost=0;
while(spfa(0,n+1,flow,cost));
三、差分约束
建图更复杂，建好图就很水了
优化：
SLF
双向队列优化 若d[v]<d[head] 插入队首 否则队尾
堆优化：手写小顶堆或者STL优先队列
优点
跑稀疏图较快且可以跑负边权
复杂度 O(E*K) K为常数且大致为1~2
题目分析：
Spfa其实很简单啊，只是建模比较麻烦了
1.首先今上午的考试题，spfa中加一个dp，存到现在点用了几个血包，但由于恶心的出题人卡了你一下，你需要一个SLF优化或者转成dijkstra
知识点：dp+优化
2.某个题目吧，大致是一个n*m的方格图，只能沿着边走，问从一个坐标到另一个坐标最少需要转几次弯。 拆点，每个格点拆为上下左右四个点，表示向哪个方向走，想到拆点之后建边就很简单了
知识点：拆点
3.一道很裸的判负环的题，方法上面又讲，代码也很简单
知识点：判负环
4.分层spfa，有一些层次，每个层次只能向下一层次建边
知识点：建模
大概见过的题目好像就只有这些了。。。
考得多的其实是拆点和建边吧
（完）