作用
给出一些形如x-y<=b不等式的约束,询问是否满足有解。
参考博客
Note
将约束为标题转换成图论里的最短路径问题
求未知数的最大值,那么按小于等于建图后求最短路
如果求未知数的最小值,那么按小于等于建图后求最长路即可。
代码实现
存储结构
const int maxn=10010;
const int inf=0x3f3f3f3f;
int n,ml,md;
int al[maxn],bl[maxn],dl[maxn];//两点与权值
int ad[maxn],bd[maxn],dd[maxn];
int d[maxn];
所需函数
Bellman-Ford(小于等于建图)
//Bellman-ford
for(int k=0;k<n;k++){
for(int i=0;i<n-1;i++){
//if(d[i+1]<inf)
d[i]=min(d[i],d[i+1]);
}
for(int i=0;i<ml;i++){
if(d[al[i]-1]<inf){
d[bl[i]-1]=min(d[bl[i]-1],d[al[i]-1]+dl[i]);
}
}
for(int i=0;i<md;i++){
if(d[bd[i]-1]<inf){
d[ad[i]-1]=min(d[ad[i]-1],d[bd[i]-1]-dd[i]);
}
}
}
例题
1)POJ - 3169 Layout
题意
农夫养了N头牛,编号为1到N。按照编号顺序排成一排,在他们之间,有一些牛关系比较好,所以希望彼此之间不超过一定距离,也有一些牛关系比较不好,希望彼此之间至少要满足某个距离。给出了ML个关系好的,以及MD个关系不好的,求1号牛和N号牛之间的最大距离。如果不存在任何一种排列方法满足条件则输出-1.无限大的情况输出-2.
AC代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10010;
const int inf=0x3f3f3f3f;
int n,ml,md;
int al[maxn],bl[maxn],dl[maxn];
int ad[maxn],bd[maxn],dd[maxn];
int d[maxn];
void solve(){
fill(d,d+n,inf);
d[0]=0;
//Bellman-ford
for(int k=0;k<n;k++){
for(int i=0;i<n-1;i++){
//if(d[i+1]<inf)
d[i]=min(d[i],d[i+1]);
}
for(int i=0;i<ml;i++){
if(d[al[i]-1]<inf){
d[bl[i]-1]=min(d[bl[i]-1],d[al[i]-1]+dl[i]);
}
}
for(int i=0;i<md;i++){
if(d[bd[i]-1]<inf){
d[ad[i]-1]=min(d[ad[i]-1],d[bd[i]-1]-dd[i]);
}
}
}
int res=d[n-1];
if(d[0]<0){
res=-1;
}
else if(res==inf){
res=-2;
}
printf("%d\n",res);
}
int main(){
scanf("%d%d%d",&n,&ml,&md);
for(int i=0;i<ml;i++) scanf("%d%d%d",&al[i],&bl[i],&dl[i]);
for(int i=0;i<md;i++) scanf("%d%d%d",&ad[i],&bd[i],&dd[i]);
solve();
return 0;
}