P1993
Aryper
·
·
个人记录
小 K 的农场
差分约束。
$a-b\ge c$ ，转变为 $b-a\le -c$ ，则建单向边 $(b,a)$ ，权值为 $-c$ 。
对于 $a-b=0$ ，看作 $a-b\le 0$ 且 $a-b\ge 0$ 即可，建一条双向边。
关于最短路为什么可以表示大小关系，可以感性理解一下。。。
$a-b\le d,b-c\le e,a-c\le f$ ，那么如果 $d+e<f$ 那么 $a-b+b-c=a-c\le d+e <f$ ，反之则 $a-c\le f<d+e$ 。
这其实就是一个松弛的过程，让整个系统满足了三角形不等式。
所以说最短路就可以求出整个差分约束系统的关系。
然后就是如何判断整个差分约束系统矛盾。
显然，$a-b\le c,a-b\ge d,c<d$ 的情况矛盾，此时 $a-b\le c,b-a\le -d,c-d<0$ ，则 $a-a\le c-d<0$ ，可以感性理解为从 $a$ 到 $a$ 的最短路小于 0 ，其实就是存在负环。
然后我也不会什么严谨证明。
比较恶心的是这题卡 dfs 判负环。。。无聊。。。
时间复杂度 $O(km)$ 。
代码：
```cpp
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;
const ll N=5e3,M=5e3;
ll n,m,a,b,c,type,flg,tot,h;
ll cnt[N+5],ver[M*2+5],nxt[M*2+5],wt[M*2+5],head[N+5],vis[N+5],f[N+5];
queue<ll> q;
void spfa(ll x) {
q.push(x);
while(!q.empty()) {
h=q.front();q.pop();vis[h]=0;
for(ll i=head[h];i;i=nxt[i]) {
if(f[ver[i]]>f[h]+wt[i]) {
f[ver[i]]=f[h]+wt[i];
cnt[ver[i]]=cnt[h]+1;
if(cnt[ver[i]]>=n) {
flg=1;break;
}
if(!vis[ver[i]]) {
vis[ver[i]]=1;q.push(ver[i]);
}
}
}
if(flg) break;
}
}
void add(ll u,ll v,ll w) {
ver[++tot]=v;wt[tot]=w;
nxt[tot]=head[u];head[u]=tot;
}
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
return ret*f;
}
void write(ll x) {
if(x<0) {x=-x;putchar('-');}
ll y=10,len=1;
while(y<=x) {y*=10;len++;}
while(len--) {y/=10;putchar(x/y+48);x%=y;}
}
int main() {
n=read();m=read();
for(ll i=1;i<=m;i++) {
type=read();
a=read();b=read();
if(type==1) {
c=read();
add(b,a,-c);
}
if(type==2) {
c=read();
add(a,b,c);
}
if(type==3) {
add(a,b,0);add(b,a,0);
}
}
for(ll i=1;i<=n;i++) {
spfa(i);
if(flg) break;
}
if(flg) printf("No");
else printf("Yes");
return 0;
}
```