题目：http://poj.org/problem?id=1201
差分约束裸题；
设 s[i] 表示到 i 选了数的个数前缀和；
根据题意，可以建立以下三个限制关系：
s[bi] >= s[ai-1] + ci ( 1 <= i <= n)
s[i] >= s[i-1] + 0 ( 1 <= i <= mx)
s[i-1] >= s[i] + (-1) (1 <= i <= mx)
然后求最长路，可以发现其中的 dis 值不会多余增大，也就满足题意要求的最小集合条件；
1A了好开心！
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int const maxn=;
int n,hd[maxn],ct,dis[maxn],mx;
bool vis[maxn];
queue<int>q;
struct N{
int to,nxt,w;
N(int t=,int n=,int w=):to(t),nxt(n),w(w) {}
}ed[maxn*];
void add(int x,int y,int z){ed[++ct]=N(y,hd[x],z); hd[x]=ct;}
void spfa()
{
memset(dis,-,sizeof dis);
dis[]=; vis[]=; q.push();
while(q.size())
{
int x=q.front(); q.pop(); vis[x]=;
for(int i=hd[x];i;i=ed[i].nxt)
{
int u=ed[i].to;
if(dis[u]<dis[x]+ed[i].w)
{
dis[u]=dis[x]+ed[i].w;
if(!vis[u])vis[u]=,q.push(u);
}
}
}
}
int main()
{
scanf("%d",&n);
for(int i=,a,b,c;i<=n;i++)
{
scanf("%d%d%d",&a,&b,&c); if(a>b)swap(a,b);
mx=max(mx,max(a,b));
add(a-,b,c);
}
mx=max(mx,n);
for(int i=;i<=mx;i++)//
{
add(i-,i,); add(i,i-,-);
}
spfa();
printf("%d",dis[mx]);
return ;
}