差分约束可以求出这样的不等式组的 ({x_i}) 的一组整数解
对于一个不等式可以移个项 (x_{a_i}le c_i+x_{b_i})
然后可以想到最短路松弛操作
用所有连接 (v) 的权值为 (w_i) 边 ((u_i,v))，用来更新 (dis_v)：
(dis_{v}=min{dis_{u_i}+w_i})
因为 (dis_v) 是取了最小的，所以对于所有连接 (v) 的权值为 (w_i) 边 ((u_i,v))，都有：
(dis_{v}le dis_{u_i}+w_i)
所以对每一个约束 (x_{a_i}le c_i+x_{b_i})，连一条 (b_i) 到 (a_i) 的边，权值为 (c_i)
这样跑完最短路，({dis_i}) 就能满足原来的不等式组了，而对于 ({dis_i+d}) 也是满足的
若有负环，则原不等式组无解
当然，不等式组的 "(le)" 都可以换成 "(ge)"，只不过变成跑最长路了（这里要注意，很容易搞错要跑最长路还是最短路，要看你的不等式的情况）
若题中既有 "(le)" 也有 "(ge)"，将 "(le)" 或 "(ge)" 的乘个 (-1) 将其统一一致
Luogu P1993 小 K 的农场
下文为表述方便，将 (a) 到 (b) 长度为 (c) 的有向边表示为 (a stackrel{c}{longrightarrow} b)
题目描述
小 K 在 MC 里面建立很多很多的农场，总共 (n) 个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共 (m) 个），以下列三种形式描述：
-
农场 (a) 比农场 (b) 至少多种植了 (c) 个单位的作物；
-
农场 (a) 比农场 (b) 至多多种植了 (c) 个单位的作物；
-
农场 (a) 与农场 (b) 种植的作物数一样多。
但是，由于小 K 的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。
思路
信息一：(x_age x_b+cimplies x_b le x_a-c)，所以连 (a stackrel{-c}{longrightarrow} b)
信息二：(x_ale x_b+c)，所以连 (b stackrel{c}{longrightarrow} a)
信息三：(x_a=x_bimplies x_a le x_b,x_b le x_a)，所以连 (astackrel{0}{longrightarrow} b) 和 (bstackrel{0}{longrightarrow} a)
判断负环时，记一个 (cnt_i) 表示起点到 (i) 的最短路上有多少个点，若大于 (n) 说明这条路径走了重复的点，也就说明有负环
#include <algorithm>
#include <utility>
#include <vector>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 5e3 + 10;
const ll inf = 1e15;
vector<pair<int,int> > edge[maxn];
int n,m,cnt[maxn];
bool vis[maxn];
ll dis[maxn];
inline bool spfa(int s) {
fill(dis,dis+maxn,inf);
queue<int> q;
vis[s] = true;
q.push(s);
dis[s] = 0;
cnt[s] = 1;
for (;q.size();) {
int now = q.front(); q.pop();
vis[now] = false;
for (size_t i = 0;i < edge[now].size();i++) {
int to = edge[now][i].first,w = edge[now][i].second;
if (dis[to] > dis[now]+w) {
dis[to] = dis[now]+w;
cnt[to] = cnt[now]+1;
if (cnt[to] > n) return false;
if (!vis[to]) {
vis[to] = true;
q.push(to);
}
}
}
}
return true;
}
int main() {
scanf("%d%d",&n,&m);
for (int i = 1,k,u,v,w;i <= m;i++) {
scanf("%d%d%d",&k,&u,&v);
if (k == 1) {
scanf("%d",&w);
edge[u].push_back(make_pair(v,-w));
}
if (k == 2) {
scanf("%d",&w);
edge[v].push_back(make_pair(u,w));
}
if (k == 3) {
edge[u].push_back(make_pair(v,0));
edge[v].push_back(make_pair(u,0));
}
}
bool ans = true;
for (int i = 1;i <= n;i++) if (!cnt[i]) ans &= spfa(i);
puts(ans ? "Yes" : "No");
return 0;
}
[SCOI2011]糖果
题目描述
幼儿园里有 (n) 个小朋友，( ext{lxhgww}) 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。同时小朋友们会提出一些如 k a b 的要求
如果 k=1， 表示第 (a) 个小朋友分到的糖果必须和第 (b) 个小朋友分到的糖果一样多；
如果 k=2， 表示第 (a) 个小朋友分到的糖果必须少于第 (b) 个小朋友分到的糖果；
如果 k=3， 表示第 (a) 个小朋友分到的糖果必须不少于第 (b) 个小朋友分到的糖果；
如果 k=4， 表示第 (a) 个小朋友分到的糖果必须多于第 (b) 个小朋友分到的糖果；
如果 k=5， 表示第 (a) 个小朋友分到的糖果必须不多于第 (b) 个小朋友分到的糖果；
思路
首先 (x_i ge 1,iin [1,n])，令 (x_0 = 0)，则 (x_i ge x_0+1)
这里我们跑最长路方便一些，所有的不等式转成 "(ge)"
k=1 ：(x_a=x_bimplies x_a ge x_b,x_b ge x_a)，连 (astackrel{0}{longrightarrow} b) 和 (bstackrel{0}{longrightarrow} a)
k=2 ：(x_a < x_b implies x_a le x_b-1 implies x_b ge x_a+1)，连 (astackrel{1}{longrightarrow} b)
k=3 ：(x_a ge x_b)，连 (bstackrel{0}{longrightarrow} a)
k=4 ：(x_a > x_b implies x_a ge x_b+1)，连 (bstackrel{1}{longrightarrow} a)
k=3 ：(x_b ge x_a)，连 (astackrel{0}{longrightarrow} b)
因为都是整数，就把 "(>)" 和 "(<)" 变成了 "(ge)" 和 "(le)"
#include <algorithm>
#include <utility>
#include <vector>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
vector<pair<int,int> > edge[maxn];
int n,k,cnt[maxn];
bool vis[maxn];
ll dis[maxn];
inline bool spfa(int s) {
queue<int> q;
vis[s] = true;
q.push(s);
dis[s] = 0;
cnt[s] = 1;
for (;q.size();) {
int now = q.front(); q.pop();
vis[now] = false;
for (size_t i = 0;i < edge[now].size();i++) {
int to = edge[now][i].first,w = edge[now][i].second;
if (dis[to] < dis[now]+w) {
dis[to] = dis[now]+w;
cnt[to] = cnt[now]+1;
if (cnt[to] > n+1) return false;
if (!vis[to]) {
vis[to] = true;
q.push(to);
}
}
}
}
return true;
}
int main() {
for (scanf("%d%d",&n,&k);k--;) {
int x,a,b;
scanf("%d%d%d",&x,&a,&b);
if (x == 1) {
edge[a].push_back(make_pair(b,0));
edge[b].push_back(make_pair(a,0));
}
if (x == 2) edge[a].push_back(make_pair(b,1));
if (x == 3) edge[b].push_back(make_pair(a,0));
if (x == 4) edge[b].push_back(make_pair(a,1));
if (x == 5) edge[a].push_back(make_pair(b,0));
if ((x == 2 || x == 4) && a == b) return printf("-1")*0;
}
for (int i = 1;i <= n;i++) edge[0].push_back(make_pair(i,1));
bool noans = spfa(0);
if (!noans) return printf("-1")*0;
long long ans = 0;
for (int i = 1;i <= n;i++) ans += dis[i];
printf("%lld",ans);
return 0;
}
Luogu P4926 [1007]倍杀测量者
题目描述
当一位选手 A 的分数不小于选手 B 的分数 (k)（(k>0)）倍时，我们称选手 A (k)倍杀了选手 B ，选手 B 被选手 A (k)倍杀了
训练前有不少选手立下了诸如“我没 (k) 倍杀选手X，我就女装”，“选手Y把我 (k) 倍杀，我就女装”的 Flag。与此同时，一些选手的成绩是已知的
Patchouli 为了维持机房秩序，放宽了选手们的 Flag 限制。Patchouli 设定了一个正常数 (T)，立下“我没 (k) 倍杀选手X就女装”的选手只要成功 ((k-T)) 倍杀了选手 X，就不需要女装。同样的，立下“选手Y把我 (k) 倍杀我就女装”的选手只要没有成功被选手Y (k+T) 倍杀，也不需要女装
Scarlet 想要确定最大的实数 (T) 使得赛后一定有选手女装
思路
首先令 (x_0 = 1)，所以已知分数的选手 A，有 (x_A = c_Ax_0implies x_A ge c_Ax_0,x_0ge frac{1}{c_A}x_A)，连 (0stackrel{c_A}{longrightarrow} A) 和 (Astackrel{frac{1}{c_A}}{longrightarrow} 0)
若要没人女装，所有的限制都应满足
对选手 B 立下 Flag 1 的选手 A 要满足 (x_A > (k-T)x_B)，连 (Bstackrel{k-T}{longrightarrow} A)
对选手 B 立下 Flag 2 的选手 A 要满足 (x_B < (k+T)x_A) 也就是 (x_A > frac{1}{(k+T)}x_B)，连 (Bstackrel{frac{1}{(k+T)}}{longrightarrow} A)
所以当无解时有人女装，二分答案 (T)，跑乘积最长路判断。
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const double eps = 1e-8;
const int maxn = 1000 + 10;
typedef long long ll;
struct flags { ll o,a,b,k; } q[maxn<<1];
vector<pair<int,double> > edge[maxn];
ll n,s,t,cnt[maxn];
double dis[maxn];
bool vis[maxn];
inline bool check(double mid) {
for (ll i = 0;i <= n;i++) {
edge[i].clear();
vis[i] = cnt[i] = dis[i] = 0;
}
for (ll i = 1;i <= s+t;i++) {
if (q[i].o == 1) edge[q[i].b].push_back(make_pair(q[i].a,1.*q[i].k-mid));
if (q[i].o == 2) edge[q[i].b].push_back(make_pair(q[i].a,1./(1.*q[i].k+mid)));
if (q[i].o == 3) {
edge[q[i].a].push_back(make_pair(0,1./q[i].k));
edge[0].push_back(make_pair(q[i].a,1.*q[i].k));
}
}
queue<ll> q;
for (;q.size();q.pop());
for (q.push(0),dis[0] = 1,vis[0] = true;q.size();) {
ll now = q.front(); q.pop();
vis[now] = false;
for (size_t i = 0;i < edge[now].size();i++) {
double w = edge[now][i].second;
ll to = edge[now][i].first;
if (dis[to] < dis[now]*w) {
dis[to] = dis[now]*w;
if ((cnt[to] = cnt[now]+1) >= n) return true;
if (!vis[to]) { q.push(to); vis[to] = true; }
}
}
}
return false;
}
signed main() {
scanf("%lld%lld%lld",&n,&s,&t);
double l = 0,r = 1e10,mid,ans = -124;
for (ll i = 1;i <= s;i++) scanf("%lld%lld%lld%lld",&q[i].o,&q[i].a,&q[i].b,&q[i].k);
for (ll i = 1;i <= t;i++) scanf("%lld%lld",&q[s+i].a,&q[s+i].k),q[s+i].o = 3;
for (;r-l >= eps;check(mid = (l+r)/2.) ? ans = mid,l = mid+eps : r = mid-eps);
if (ans < 0) printf("-1");
else printf("%.9lf",ans);
return 0;
}