【模板】差分约束

大致题意：

给你这样的一个式子（其中y的值是给定的）：

$$\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases}$$

求满足关系的一个x的集合

思路

这类题型是由一个方程组的解转化成图论中边的问题的。 形如这样的一个式子：

• $x_c-x_{c'}\leq y$

我们进行移项后变成了这样

$x_c\leq y+x_{c'}$

类比于在图论中，我们更新节点的距离的公式

当满足：$d_u> y+d_v$

我们才去对节点的信息进行更新

=》求单源最短路的过程就是让式子从 $d_u> y+d_v$ 转化成 $d_u\leq y+d_v$ 的过程。

就可得 $x_c-x_{c'}\leq y$ 其实是描述一个节点$x_{c'}$到节点$x_c$有一条距离为y的路径。

然后，我们添加一个超级节点n,让n可以走向所有节点，并且距离为0。

这样我们就可以用单源最短路的算法去在图上寻找超级节点到各个节点的最短路了。

因为某些题的数据会出现负数，所以这里使用SPFA算法寻找最短路。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+12,inf=1e+12;
int head[N],a[N],dis[N],cnt,vis[N];
int n,m,u,v,w;

struct {
  int to,nex,w;
}edge[N];

void addedge(int u,int v,int w)
{
  ++cnt;
  edge[cnt].to=v;
  edge[cnt].nex=head[u];
  edge[cnt].w=w;
  head[u]=cnt;
}
queue<int>q;
int spfa(){

  dis[n+1]=0;
  vis[n+1]=1;
  a[n+1]++;
  q.push(n+1);
  while( !q.empty() )
  {
    int y=q.front();
    q.pop();
    vis[y]=0;
    for(int i=head[y];i;i=edge[i].nex)
    {
      int x=edge[i].to,w=edge[i].w;
      if( dis[x]>dis[y]+w )
      {
        dis[x]=dis[y]+w;
        if( !vis[x] )
        {
          q.push(x);
          vis[x]=1;
          a[x]++;
          if( a[x]>=n+1 )
            return 0;
        }

      }

    }

  }
  return 1;

}

int main(){
   cin>>n>>m;
  for(int i=1;i<=n;i++)
    dis[i]=INT_MAX;
   while(m--)
   {
     cin>>u>>v>>w;
     addedge(v,u,w);
   }
      for(int i=1;i<=n;i++)
   {
     addedge(n+1,i,0);
   }
  if( spfa() )
  {
    for(int i=1;i<=n;i++)
      cout<<dis[i]<<" ";
  }
  else cout<<"NO";




}