原题：ZOJ 3668 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3668
典型差分约束题。
将sum[0] ~ sum[n] 作为节点，A<=sum[R]-sum[L-1]<=B可以分别建边：
x(L-1)-->xR w = B
xR --> x(L-1) w = -A
注意还有 -10000<=sum[i]-sum[i-1]<=10000 (for i in (2,n)),所以相邻点之间还要建边，（WA了很多次）这样的话就不用另加节点来使联通了，因为必会连通。如果出现负环，则无解。
用SPFA求最短路并判负环，求出的节点的dis[i]如果为INF，则任意取值（事实上此题不会），否则dis[i]就是sum[i]，然后根据sum数组两两之间差值来求出a[i]。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#define Mod 1000000007
using namespace std;
#define N 10017 vector<pair<int,int> > G[N];
int dis[N],inq[N],cnt[N];
int sum[N];
int n,m;
queue<int> que; bool SPFA(int s)
{
int u,v,i,w;
for(i=;i<=n;i++)
{
inq[i] = ;
dis[i] = Mod;
cnt[i] = ;
}
while(!que.empty())
que.pop();
que.push(s);
dis[s] = ;
cnt[s] = ;
inq[s] = ;
//for(i=0;i<=n;i++)
//que.push(i);
while(!que.empty())
{
u = que.front();
que.pop();
inq[u] = ;
for(i=;i<G[u].size();i++)
{
v = G[u][i].first;
w = G[u][i].second;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
if(!inq[v])
{
inq[v] = ;
cnt[v]++;
if(cnt[v] >= n+)
return false;
que.push(v);
}
}
}
}
return true;
} int main()
{
int i,j;
int L,R,A,B;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=;i<=n+;i++)
G[i].clear();
while(m--)
{
scanf("%d%d%d%d",&L,&R,&A,&B);
G[R].push_back(make_pair(L-,-A));
G[L-].push_back(make_pair(R,B));
}
for(i=;i<=n;i++)
{
G[i].push_back(make_pair(i-,));
G[i-].push_back(make_pair(i,));
}
if(SPFA())
{
for(i=;i<=n+;i++)
{
if(dis[i] != Mod)
sum[i] = dis[i];
else
sum[i] = sum[i-];
}
printf("%d",sum[]);
for(i=;i<=n;i++)
printf(" %d",sum[i]-sum[i-]);
printf("\n");
}
else
puts("The spacecraft is broken!");
}
return ;
}