差分约束
wangyitong
2018-09-26 19:22:37
哇，没搞清楚这个，结果被黄牌题吊打。。。。
差分约束系统是用来解一些特殊的不等式。
就是把每个约束条件建边，然后跑最短路或者最长路。
例如：
$x_{i}$ $-$ $x_{j}$>=k; 那么就从j向i连一条长度为k的边；跑最长路。
$x_{i}$ $-$ $x_{j}$<=k; 那么就从j向i连一条长度为k的边；跑最短路。
对于不同的题，跑最短路和最长路是不一样的，要看约束条件。
例题：[p1250——种树](https://www.luogu.org/problemnew/show/P1250)
这题就是用前缀和列出不等式，然后全部变成$x_{i}$ $-$ $x_{j}$>=k这一类型，然后跑最长路就是最后的答案了。
```cpp
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=30005;
int head[N];
bool used[N];
int dis[N],n,m,tot,x,y,z;
struct node
{
int next,value,to;
}edge[N*100];
void add(int x,int y,int z)
{
tot++;
edge[tot].to=y;
edge[tot].value=z;
edge[tot].next=head[x];
head[x]=tot;
}
void spfa(int x)
{
memset(dis,-63,sizeof(dis));
queue<int>Q;
Q.push(x);
dis[x]=0;
while(!Q.empty())
{
int y=Q.front();Q.pop();used[y]=0;
for(int i=head[y];i;i=edge[i].next)
{
if(dis[edge[i].to]<dis[y]+edge[i].value)
{
dis[edge[i].to]=dis[y]+edge[i].value;
if(!used[edge[i].to])
{
used[edge[i].to]=1;
Q.push(edge[i].to);
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x-1,y,z);
}
for(int i=1;i<=n;i++)
{
add(i-1,i,0);
add(i,i-1,-1);
}
memset(used,0,sizeof(used));
spfa(0);
printf("%d",dis[n]);
return 0;
}
```
只要题意可以变成许多个限制条件，然后就可以用差分约束了。
注意一般要用spfa，因为会有负环。
有负环说明这个方程组无解。
顺便说一下，怎么判无解吧.
一个点被入队n次就说明出现负环了。
不要让我这个蒟蒻证明~~（不会）~~（逃