差分约束系统，求最小值，跑最长路。
转自：https://www.cnblogs.com/ehanla/p/9134012.html
题解：设sum[x]为前x个咕咕中至少需要赶走的咕咕数，则sum[b]−sum[a−1]>=c表示[a,b]区间至少赶走c只。题目中选择的是最少，我们需要跑最长路，因存在负边，所以以SPFA进行操作。
d[v]>=d[u]+w，前面我们可以推出第一个式子sum[b]>=sum[a−1]+c，但是如果只连这些边，整张图连通不起来。我们发现i和i+1存在关系0<=sum[i+1]−sum[i]<=1，这个其实就是表示i+1那个位置赶与不赶。
推出第二个和第三个式子：sum[i]>=sum[i+1]−1，sum[i+1]>=sum[i]+0
由以上式子得到边：a−1点 b点 距离c
i+1点 i点 距离−1
i点 i+1点 距离0
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
const int N=2e5+;
int n,k,cnt;
bool vis[N];
int head[N],d[N];
struct node
{
int to,next,w;
}edge[N]; void init()
{
cnt=;
memset(head,-, sizeof(head));
} void add(int u,int v,int w)
{
edge[cnt].to=v;edge[cnt].w=w,edge[cnt].next=head[u];head[u]=cnt++;
} void spfa()
{
memset(d,-INF,sizeof(d));
memset(vis,,sizeof(vis));
queue<int> q;
q.push();
d[]=;
vis[]=;
while(q.size())
{
int u=q.front();q.pop();
vis[u]=; // 可以重复入队，现在不在队内
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if(d[v]<d[u]+edge[i].w) // 最长路径
{
d[v]=d[u]+edge[i].w;
if(!vis[v])
{
q.push(v);
vis[v]=;
}
}
}
}
} int main()
{
init();
cin>>k>>n;
for(int i=;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
// d[b]-d[a-1] >= c
add(a-,b,c);
}
// 0 <= d[i+1]-d[i] <= 1
for(int i=;i<k;i++)
{
add(i,i+,);
add(i+,i,-); // 存在负数权值
}
spfa();
cout<<d[k]<<endl;
return ;
}
求单源最短路的算法SPFA：
算法中需要的变量
int N; //表示n个点，从1到n标号
int s,t; //s为源点，t为终点
int d[N]; //d[i]表示源点s到点i的最短路
int pre[N]; //记录路径（或者说记录前驱）
queue <int> q; //队列，
bool vis[N]; //vis[i]=1表示点i在队列中 vis[i]=0表示不在队列中
在整个算法中有顶点入队要记得标记vis数组，有顶点出队记得消除那个标记，顶点可以重复入队，这区别于dijkstra算法
队列+松弛操作：
读取队头顶点u，并将队头顶点u出队(消除标记)；将与点u相连的所有点v进行松弛操作，如果能更新估计值（使d[v]变小），那么就更新，另外，如果点v没有在队列中，那么要将点v入队（记得标记），如果已经在队列中了，那么就不用入队
以此循环，直到队空为止就完成了单源最短路的求解
SPFA可以处理负权边
SPFA判断负环：如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）
int spfa_bfs(int s)
{
queue<int> q;
memset(d,0x3f, sizeof(d)); // 距离矩阵
memset(c,,sizeof(c)); // 入队次数
memset(vis,, sizeof(vis));
q.push(s);
vis[s]=;
c[s]++;
int OK=;
while(q.size())
{
int u=q.front();q.pop();
vis[u]=;
for(int i=head[u];i;i=next[i])
{
int v=ver[i];
if(d[v]>d[u]+w[i])
{
d[v]=d[u]+w[i];
if(!vis[v])
{
vis[v]=;
q.push(v);
c[v]++;
if(c[v]>N) // 超过入队次数上限，说明有负环
return OK=;
}
}
}
}
return OK;
}
Dijkstra的priority_queue写法与SPFA的queue写法对比:
- Dijkstra+heap是用小根堆，每次取出d中未访问的最小点，来更新距离，对于这个点来说，最小距离就是当前的d。
- SPFA是用双端队列，每次取出队头，来更新距离，它之后可能还会入队。是一种动态逼近法，因为每次松弛距离都会减小，所以松弛一定会有结束。如果一个点入队超过n次就存在负环。
Dijkstra
用STL中的优先队列实现堆：
while(优先队列非空)
-->队头出队，松弛它的边
-->松弛了的pair<新距离,点>入队
typedef pair<int,int> P;
priority_queue<P,vector<P>,greater<P> > q; // 最小堆
...
while(!q.empty()){ // O(V) 加上count<n可以优化一点点
int w=q.top().first, u=q.top().second;
q.pop(); // O(lgV)
if(vis[u])continue; vis[u]=true;
//++count;
for(int i=head[u];i;i=edge[i].next){ // Sum -> O(E)
int v=edge[i].to;
if(d[v]>d[u]+edge[i].w){
d[v]=d[u]+edge[i].w;
q.push(P(d[v],v)); // O(lgV)
}
}
}
SPFA：
while(队非空)
-->队头出队，取消标记，松弛它的边
-->松弛了且不在队内的点入队，并标记
while(!q.empty()){
int u=q.front(); q.pop();
vis[u]=false;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if(d[v]>d[u]+edge[i].w){
d[v]=d[u]+edge[i].w;
if(!vis[v])vis[v]=true,q.push(v);
}
}
}
Dijkstra和Prim也很相似，它们的区别主要是d的含义，前者是到s的临时最短距离[s->每一点]，后者是到树的临时最短距离[边长]，相同点是，每次找最小的d更新其它点的距离。