本文主要是介绍(Luogu) P1993 小K的农场 (差分约束)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
解题思路：这是一道差分约束的裸题，我也是第一次接触差分约束，（详细解说戳我）简单来说，就是将不等式 与 spfa里的松弛操作联系起来，给予他意义，这样就可以用图的方式来解决他了，观察等式 a-b<=k ,这个式子可以变成 a<=b+k 这个式子是不很像
spfa里的松弛操作
if(d[v] < d[u] + w(u,v) ) {d[v] = d[u] + w(u, v);
}我们可以将a看成d[v], b看成d[u], 那么k就是u到v这条边上的权值了，然后就可以建图。
而这个题目，他给的至多和至少就是这样的不等式（都化简成小于等于），而等于，那就建两条权值为0的边，然后可以还是不可以呢，那就判断有没有环，有环那就矛盾了。深搜判断环比宽搜快很多。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int maxn=1e4+5;
int n,m;
struct node {int to,w;
};
vector<node> eg[maxn];
int dist[maxn],vis[maxn];
bool spfa(int st) {vis[st]=1;int to,w;node tp;for(int i=0; i<(int)eg[st].size(); ++i) {tp=eg[st][i];to=tp.to,w=tp.w;if(dist[to]>dist[st]+w) {dist[to]=dist[st]+w;if(vis[to] || spfa(to)) return 1;}}vis[st]=0;return 0;
}
int main() {std::ios::sync_with_stdio(0);cin>>n>>m;int x,a,b,c;for(int i=1; i<=m; ++i) {cin>>x;if(x==1) {cin>>a>>b>>c;eg[a].push_back(node {b,-c});}if(x==2) {cin>>a>>b>>c;eg[b].push_back(node {a,c});}if(x==3) {cin>>a>>b;eg[a].push_back(node {b,0});eg[b].push_back(node {a,0});}}for(int i=1;i<=n;++i){if(spfa(i)){cout<<"No"<<endl;return 0;}} cout<<"Yes"<<endl;return 0;
}
这篇关于(Luogu) P1993 小K的农场 (差分约束)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
