这是一道 最短路+差分约束
差分约束我还不是很熟悉。但就是通过题目中给予我们的不等关系来写出不等式，这里不等式的形式是（xi-xj<=a） 我们可以将题目中给出的所有关系写成不等式在通过不等式构造出一张图。注意和向量相似，我们在用题目中给予的关系构造图的时候是箭头减去箭尾。 就拿刚才那个不等式来说 （xi-xj<=a）通过这不等式我们可以构造出一条有向边<j,i>，他的权值是a，然后xi，和xj就分别代表最短路中从源点到点i（j）的最短路劲。然后我们在自己加入一个源点就可以吧差分约束的类型的题目转化成为一道最短路径的题目。
以这道题目为例子。
题目中给了我们每一个军营的上限，和从第i到第j个军营的人数下限，从而我们可以写出多组不等式
Xi - Xi-1<=d[i]-d[i-1] 此处d【i】表示从0到i最多有多少士兵
Xi - Xi-1>=0 (这组我们可以在两边乘以一个-1 ： 就转变成了我们要的形式 Xi-1 - Xi<=0) 表示每个军营人数大于等于0
Xj - Xi-1 >=num[i....j] 转化后 Xi-1 - Xj <=num[i...j] 此处num[i.....j]表示军营i到军营j这一区间士兵最少的人数。
Xj - Xi-1<=d[j]-d[i-1] 表示i到j这区间士兵最多人数是多少。
完成建图后加入点0 ，初始化 dis[0]=0;
然后用spfa求最短路劲，注意这里起点是n，因为要求全部兵营至少多少人 列出关系 Xn-X0>=a 转化成标准形式 X0-Xn<=-a 我们可以看出来 这条边是<n,0> ，而不是
<0,n>，所以起点是n. 我们所求的目标也就成了dis[0],因为初始化源点为0所以a就是-dis[0]
Memory Limit: 65536 KB
It is well known that, in the period of The Three Empires, Liu Bei, the emperor of the Shu Empire, was defeated by Lu Xun, a general of the Wu Empire. The defeat was due to Liu Bei's wrong decision that he divided his large troops into a number of camps,
each of which had a group of armies, and located them in a line. This was the so-called "Linked Camps".
Let's go back to that time. Lu Xun had sent many scouts to obtain the information about his enemy. From his scouts, he knew that Liu Bei had divided his troops into n camps, all of which located in a line, labeled by 1..n from left to right. The ith camp
had a maximum capacity of Ci soldiers. Furthermore, by observing the activities Liu Bei's troops had been doing those days, Lu Xun could estimate the least total number of soldiers that were lived in from the ith to the jth camp. Finally, Lu Xun must estimate
at least how many soldiers did Liu Bei had, so that he could decide how many troops he should send to burn Liu Bei's Linked Camps.
Input:
There are multiple test cases! On the first line of each test case, there are two integers n (0<n<=1,000) and m (0<=m<=10,000). On the second line, there are n integers C1������Cn. Then m lines follow, each line has three integers i, j, k (0<i<=j<=n, 0<=k<2^31),
meaning that the total number of soldiers from the ith camp to the jth camp is at least k.
Output:
For each test case, output one integer in a single line: the least number of all soldiers in Liu Bei's army from Lu Xun's observation. However, Lu Xun's estimations given in the input data may be very unprecise. If his estimations cannot be true, output
"Bad Estimations" in a single line instead.
Sample Input:
3 2 1000 2000 1000 1 2 1100 2 3 1300 3 1 100 200 300 2 3 600
Sample Output:
1300 Bad Estimations
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 1100
#define INF 0xFFFFFF
struct node
{
int to;
int dis;
};
vector<node> g[MAXN];
bool in[MAXN];
int dis[MAXN];
int num[MAXN];
int n,m;
int counts[MAXN];
bool spfa(int s)
{
queue<int> q;
for(int i=0;i<=n;i++)
{
in[i]=false;
dis[i]=INF;
counts[i]=0;
}
dis[0]=0;
in[s]=true;
dis[s]=0;
counts[s]++;
q.push(s);
while(!q.empty())
{
int tag=q.front();
q.pop();
in[tag]=false;
for(int i=0;i<g[tag].size();i++)
{
int j=g[tag][i].to;
if(dis[j]>dis[tag]+g[tag][i].dis)
{
dis[j]=dis[tag]+g[tag][i].dis;
if(!in[j])
{
in[j]=true;
q.push(j);
counts[j]++;
if(counts[j]>=(n+1))
return false;
}
}
}
}
return true;
}
void init()
{
int s,e,nn;
node temp;
for(int i=0;i<=n;i++)
g[i].clear();
num[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
num[i]+=num[i-1];
}
for(int i=1;i<=n;i++)
{
temp.to=i;
temp.dis=num[i]-num[i-1];
g[i-1].push_back(temp);
temp.to=i-1;
temp.dis=0;
g[i].push_back(temp);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&s,&e,&nn);
temp.to=s-1;
temp.dis=-nn;
g[e].push_back(temp);
temp.to=e;
temp.dis=num[e]-num[s-1];
g[s-1].push_back(temp);
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
if(spfa(n))
cout<<-dis[0]<<endl;
else
cout<<"Bad Estimations"<<endl;
}
return 0;
}