关键词：
奶牛的身高
题目描述：
奶牛们在FJ的养育下茁壮成长。这天,FJ给了奶牛Bessie一个任务,去看看每个奶牛场中若干只奶牛的身高,由于Bessie是只奶牛,无法直接看出第i只奶牛的身高,而只能看出第i只奶牛与第j只奶牛的身高差,其中第i 只奶牛与第j只奶牛的身高差为A(i<=n)。当A大于0时表示这只奶牛比前一只奶牛高A cm,小于0时则是低。现在,FJ让Bessie总共去看了m次身高,当然也就传回给FJ m对奶牛的身高差,但是Bessie毕竟是奶牛,有时候眼睛可能会不好使……(大雾)你的任务是帮助FJ来判断是不是需要给Bessie看看眼睛了……
注:Hj-Hi=A 注意T1的样例 注意注意注意 重要的事情说三遍。
输入描述：
第一行为一个正整数w,表示有w组数据,即w个奶牛场,需要你判断。每组数据的第一行为两个正整数n和m,分别表示对应的奶牛场中的奶牛只数以及看了多少个对奶牛身高差。接下来的m行表示Bessie看m次后传回给FJ的m条信息,每条信息占一行,有三个整数s,t和v,表示第s只奶牛与第t只奶牛的身高差为v。
输出描述：
包含w行,每行是”Bessie’s eyes are good”或”Bessie is blind.”(不含双引号),其中第i行为”Bessie’s eyes are good”当且仅当第i组数据,即无法从第i个奶牛场传回的身高差判断Bessie视力好不好;第i行为”Bessie is blind.”当且仅当第i组数据,即从第i个奶牛场传回的身高差是有问题的。
样例输入：
2
3 3
1 3 10
2 3 5
1 2 5
4 3
1 4 100
3 4 50
1 3 100
样例输出：
Bessie’s eyes are good
Bessie is blind.
数据范围及提示：
对于30%的数据,保证n<=100,m<=1000;
对于100%的数据,保证w<=100,n<=1000,m<=30000,|A|<=30000.
思路：
差分约束的变形，如果a-b=x,b-c=y,a-c=z,则1式+2式为：a-c=x+y，只需判断x+y是否等于z即可，这与差分约束的思路是一样的，那么这道题就成了一道图论题，用spfa即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=100010;
const int inf=0x7fffffff;
struct node
int to;
int w;
int next;
e[maxn*2];
queue<int> q;
bool can,flag[maxn];
int t,n,m,tot,head[maxn],dis[maxn];
void add_edge(int u,int v,int w)
tot++;
e[tot].to=v;
e[tot].w=w;
e[tot].next=head[u];
head[u]=tot;
bool spfa(int u)
while(!q.empty()) q.pop();
flag[u]=1;q.push(u);
while(!q.empty())
u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=e[i].next)
int v=e[i].to;
if(flag[v])
if(dis[v]!=dis[u]+e[i].w)
return 1;
dis[v]=dis[u]+e[i].w;
if(!flag[v])
q.push(v);
flag[v]=1;
return 0;
int main()
int x,y,z;
scanf("%d",&t);
while(t--)
memset(head,0xfff,sizeof(head));
memset(flag,0,sizeof(flag));
memset(dis,0,sizeof(dis));
cin>>n>>m;tot=0;can=0;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&x,&y,&z);
add_edge(x,y,z);
add_edge(y,x,-z);
for(int i=1;i<=n;i++)
if(spfa(i))
puts("Bessie is blind.");
can=1;
break;
if(!can)
puts("Bessies eyes are good");
return 0;
pku3169layout(差分约束系统+bellmanford)
题目大意：原题链接当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。FJ有N（2<=N<=1000）头奶牛，编号从1到N，沿一条直线站着等候喂食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条，所以可能有... 查看详情
tallestcow，题解(代码片段)
...意： 问满足一系列形如ab可以相互看到的约束的所有奶牛的最大身高（最高的编号和高度已给出）分析： 首先，这个可以互相看到指的是中间的人比两头的都矮，一条斜线看到的不行，那么其实我们就可以直接默认每个... 查看详情
4246奶牛的身高
题目描述 Description 奶牛们在FJ的养育下茁壮成长。这天,FJ给了奶牛Bessie一个任务,去看看每个奶牛场中若干只奶牛的身高,由于Bessie是只奶牛,无法直接看出第i只奶牛的身高,而只能看出第i只奶牛与第j只奶牛的身高差,其... 查看详情
tallestcow，题解(代码片段)
...意： 问满足一系列形如ab可以相互看到的约束的所有奶牛的最大身高（最高的编号和高度已给出）分析： 首先，这个可以互相看到指的是中间的人比两头的都矮，一条斜线看到的不行，那么其实我们就可以直接默认每个... 查看详情
奶牛排队(代码片段)
题意 【问题描述】奶牛在熊大妈的带领下排成了一条直队。显然，不同的奶牛身高不一定相同……现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛A是最矮的，最右边的B是最高的，且B高于A奶牛，... 查看详情
奶牛排序——rmq(代码片段)
【问题描述】奶牛在熊大妈的带领下排成了一条直队。显然，不同的奶牛身高不一定相同……现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛A是最矮的，最右边的B是最高的，且B高于A奶牛，且中间如果存在... 查看详情
woj1109奶牛排队(代码片段)
题目链接：WOJ1109题目描述：奶牛在熊大妈的带领下排成了一条直队。显然，不同的奶牛身高不一定相同……现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛A是最矮的，最右边的B是最高的，且B高于A奶牛，且... 查看详情
差分约束系统
差分约束的定义： 差分约束系统是一种特殊的一元一次不等式组，约束条件就是一些以两个变量做差的形式构成，形如Xi-Xj<=Ck（Ck为常数，是一个已知的量），我们所需要求一组解，使得所有的约束条件的不等式都得到满... 查看详情
差分约束系统
差分 差分就是一种找出不等式然后将不等式转化为解题方法的算法。差分的关键构造不等式通过不等式连边差分约束系统中源点到每个点的距离确定关于Dist[]的初始化如果将源点到各点的距离初始化为0，最终求出的最短路... 查看详情
差分约束(代码片段)
一、何为差分约束系统：差分约束系统（systemofdifferenceconstraints），是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束... 查看详情
差分约束讲解(代码片段)
差分约束讲解——byysy1.前置知识????????因为差分约束是基于(spfa)的一种解不等式，或等式组的技巧，所以差分约束的前置知识就是(spfa)和对不等式的简单小变换。2.讲解?????????因为差分约束只是一个技巧，所以在这里我先讲解技... 查看详情
差分约束系统
差分约束系统： 差分约束系统就是给了你一些不等的关系，然后通过转化把每个关系转化成x-y<=d的形式，然后问你是否有满足所有不等式的解，并求最大最小解。这类问题的神奇之处是可以转化成图论中的最短路问题求解... 查看详情
差分约束模板(代码片段)
差分约束系统百度百科：如果一个系统由n个变量和m个约束条件组成，形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统(systemofdifferenceconstraints)。亦即，差分约束系统是求解关于一组变量的特殊不... 查看详情
差分约束
...合法方案或者让你求出合法方案。——————————差分约束·前言: 一个概括的定义是,一些不等式组可以视作一个差分约束系统。简单而言,就是给出许多不等式,然后我们需要给每个未知数填上值,使... 查看详情
初涉差分约束系统(代码片段)
一个把数学问题转化为图论模型的很好的例子差分约束系统差分约束系统的定义是：一个由$n$个变量和$m$个约束条件组成，形成$m$个形如$x_i-x_j≤k$的不等式($i,j∈[1,n],k$为常数)的系统。举个例子（图自网络）：例如这个不等... 查看详情
有关差分约束系统
差分约束系统详解（极力推荐）==> http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html个人瞎想:差分约束系统的题最重要的就是充分利用题目条件建立模型、构造出不等式最后使用最短路来算出答案，当然有些题目即使构造... 查看详情
关于图论差分约束
...，我已经找不到可以优化的，所以说就看看他的解释吧~//差分约束的重点中的重点：约束式一定要化为y<=x+c的形式，否则模型直接的转换会出错/*差分约束系统的定义如果一个系统由n个变量和m个约束条件组成，其中每个约束... 查看详情
差分约束系统--详讲
------------差分约束题目请戳：差分约束题集暨报告总的开说差分约束问题就是给出一系列不等式然后求问某一式子的最大值或者最小值。差分约束问题具体解释： 比方有这样一组不等式： X1-X2<=0 X... 查看详情