给你一个含有$n$个未知数$m$个不等式的不等式组，求满足此不等式组的一组解。
-----------------------
我们拿一个不等式举例：$X_{i}-X_{j}\leq C_{k}$。
这和最短路算法里的松弛操作比较像：dis[to]>=dis[now]+edge[i].dis。所以我们可以将其转化为图：从$j$点到$i$点连一条长度为$d$的边。
有时候我们可以建立一个超级源点，来求得这组不等式的最小（大）解。即从$0$点到$i$点连一条长度为$0$的边，从$0$点跑最短路即可。
记得要判定图里是否有环，因为如果图里有环这组不等式是无解的。
给一道模板题：题目描述
--------------------------------------------
差分约束裸题，直接上代码：
#include<bits/stdc++.h> using namespace std; int n,m,head[50005],cnt,u,v,d,c[50005]; int vis[50005],dis[50005]; struct node { int next,to,dis; }edge[50005]; void add(int from,int to,int dis) { edge[++cnt].next=head[from]; edge[cnt].to=to; edge[cnt].dis=dis; head[from]=cnt; } void spfa(int x) { queue<int> q; memset(dis,0x3f3f3f3f,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(c,0,sizeof(c)); q.push(x);dis[x]=0;vis[x]=1; while(!q.empty()) { int now=q.front();q.pop();vis[now]=0; for (int i=head[now];i;i=edge[i].next) { int to=edge[i].to; if (dis[to]>dis[now]+edge[i].dis) { dis[to]=dis[now]+edge[i].dis; c[to]=c[now]+1; if (c[to]>=n) { cout<<"NO"; exit(0); } if (!vis[to]) { q.push(to); vis[to]=1; } } } } } int main() { cin>>n>>m; for (int i=1;i<=m;i++) cin>>u>>v>>d,add(v,u,d); for (int i=1;i<=n;i++) add(0,i,0); spfa(0); for (int i=1;i<=n;i++) cout<<dis[i]<<" "; return 0; }
差分约束的条件不会一眼能看出来，我们要学会转化。
题目：LMX的攻城游戏
题目大意：给定一段长度为$n$的数列，有$m$个条件。每个条件给定一个三元组$a,b,c$，表示从$a$到$b$至少有$c$。问序列和最小是多少。
---------------------------------
题目转化：$S_{b}-S_{a-1}\leq c$ 。
其实题目里面还有一个隐藏条件，即$S_{i+1}-S_{i}\leq 1$。
有了这些条件，这道题就可以转化为差分约束处理了。
代码：
#include<bits/stdc++.h> using namespace std; int vis[100005],dis[100005],n,m; int head[500005],cnt; struct node{ int next,to,dis; }edge[500005]; inline int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void add(int from,int to,int dis) { edge[++cnt].next=head[from]; edge[cnt].to=to; edge[cnt].dis=dis; head[from]=cnt; } void spfa() { queue<int> q; dis[0]=0;vis[0]=1;q.push(0); while(!q.empty()) { int now=q.front();vis[now]=0;q.pop(); for (int i=head[now];i;i=edge[i].next) { int to=edge[i].to; if (dis[to]>dis[now]+edge[i].dis) { dis[to]=dis[now]+edge[i].dis; if (!vis[to]){ q.push(to); vis[to]=1; } } } } } int main() { n=read(),m=read(); for (int i=1;i<=n;i++) dis[i]=i; for (int i=1;i<=m;i++) { int u=read(),v=read(),d=read(); add(u-1,v,-d); } for (int i=1;i<=n;i++) add(i,i-1,1),add(i-1,i,0); spfa(); printf("%d",-dis[n]); return 0; }
原文链接: https://www.cnblogs.com/Invictus-Ocean/p/12494664.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/373228
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
