题解 P1993 【小K的农场】
command_block
2018-12-29 15:31:41
复习了**差分约束**，顺手写个题解。
所谓差分约束问题，就是用图论解一些特殊不等式的操作。
假设有n个变量，形如$\Large{x_1,x_2,x_3...x_n}$
满足一些不等式：
$\Large{x_{a_1}-x_{b_1}>=c_1}$
$\Large{x_{a_2}-x_{b_2}>=c_2}$
$……$
$\Large{x_{a_3}-x_{b_3}>=c_3}$
就是说某变量与某变量的差大于(等于)某某。
咋一看没什么头绪，不过某位天才一拍脑门，想到了图论中的**最短路**，并成功建模。
大家学单源最短路的时候，想必都处理过$dis$数组，其满足一个称为“三角不等式”的东西：
对于一条边来讲
$\large{dis[to]<=dis[from]+length}$
想想最短路的“松弛”就理解了。
变形可得:
$\large{dis[from]-dis[to]>=-length}$
也就是说每条边其实对应着**dis数组中的一个不等式限制**。
这可以用来求解差分约束。
题目中的限制：
1.$\large{dis_a-dis_b>=c}$
建边$a->b$权值为$-c$
2.$\large{dis_a-dis_b<=c}$
变形可得:
$\large{dis_b-dis_a>=-c}$
建边$b->a$权值为$c$
3.$\large{dis_a==dis_b}$
转化可得:
$\large{dis_b-dis_a>=0}\ $ 与 $\ \large{dis_b-dis_a<=0}$
建边$b->a$与$a->b$权值为$0$。
如何判断无解呢？
我们是按照最短路建的模，最短路无解就是对应**负环**。
反映到代数上就是变量无限小。
建出的图不一定连通，所以要做一番操作(超级汇点也行，多次spfa也行)
这里跟大家分享一个spfa判负环的小技巧，每次扫边集的时候记录工作次数，估摸着快要TLE了就认为有负环。
好像是称为**卡带**优化。
做题的时候很好用，但是比赛时慎用。
(~~比如说某场比赛考了这道原题，我卡带设小了，没了80分~~)
Code：
```cpp
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int n,m,ord,aaa,from,to,len,s[10500];
vector<int> g[10500],l[10500];
queue<int> t;
bool in[10500];
void addLine(int from,int to,int len)
{
g[from].push_back(to);
l[from].push_back(len);
}
bool spfa()
{
for (int i=1;i<=n;i++)
{t.push(i);in[i]=1;}
while(!t.empty()){
if (aaa>5000000)return 1;//卡带
int u=t.front();
aaa+=g[u].size();
t.pop();in[u]=0;
//printf("%d %d\n",u,t.size());
for (int i=0,v;i<g[u].size();i++)
if (s[v=g[u][i]]>s[u]+l[u][i]){
s[v]=s[u]+l[u][i];
if (!in[v]){t.push(v);in[v]=1;}
}
}return 0;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
scanf("%d%d%d",&ord,&from,&to);
//x-y>=-c change-into x->y(c)
if (ord==1){
scanf("%d",&len);
addLine(from,to,-len);
//from-to>=len
}if (ord==2){
scanf("%d",&len);
addLine(from,to,len);
//from-to<=len -> from-to>=-len
}if (ord==3){
addLine(from,to,0);
addLine(to,from,0);
// from-to==0 -> from-to>=0 && from-to>=0
}
}
if (spfa())printf("No");
else printf("Yes");
return 0;
}
```