Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
有一个整数序列,我们不知道她的长度是多少(即序列中整数的个数),但我们知道在某些区间中至少有多少个整数,用区间
[ai,bi,ci]来描述它,[ai,bi,ci]表示在该序列中处于[ai,bi]这个区间的整数至少有ci个。现在给出若干个这样的区间,
请你求出满足条件的最短序列长度是多少。如果不存在则输出 -1。
【输入格式】
第一行包括一个整数n(n<=1000),表示区间个数;
以下n行每行描述这些区间,第i+1行三个整数ai,bi,ci,由空格隔开,其中0<=ai<=bi<=1000 而且 1<=ci<=bi-ai+1。
【输出格式】
文件输出只有一个整数表示满足要求序列长度的最小值。
Sample Input
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
Sample Output
6
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t081
【题解】
差分约束系统;
题解同:http://blog.csdn.net/harlow_cheng/article/details/53442866
按照所给的关系式,要求的是最长路;
如果无解,是因为出现了正权环吧.出现环可以用入队次数来判断,如果入队次数大于1000就输出无解吧;
其他一样;
注意改成[a[i],b[i]+1);
【完整代码】
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define pb push_back
const int MAXN = 1000+100;
int n,a[MAXN],b[MAXN],c[MAXN],in[MAXN],s=MAXN,t = 0,dis[MAXN];
vector <int> g[MAXN],w[MAXN];
queue <int> dl;
bool exsit[MAXN];
void add(int x,int y,int z)
{
g[x].pb(y);
w[x].pb(z);
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
scanf("%d",&n);
for (int i = 1;i <= n;i++)
{
scanf("%d%d%d",&a[i],&b[i],&c[i]);
b[i]++;
add(a[i],b[i],c[i]);
s = min(s,a[i]); t = max(t,b[i]);
}
for (int i = 1;i <= 1001;i++)
{
add(i-1,i,0);
add(i,i-1,-1);
}
for (int i = 0;i <= 1001;i++)
dis[i] = -0x3f3f3f3f;
dis[s] = 0;
dl.push(s);
exsit[s] = true;in[s]++;
while (!dl.empty())
{
int x = dl.front();
dl.pop();exsit[x] = false;
int len = g[x].size();
for (int i = 0;i <= len-1;i++)
{
int y = g[x][i],co = w[x][i];
if (dis[y]<dis[x]+co)
{
dis[y] = dis[x]+co;
if (!exsit[y])
{
in[y]++;
if (in[y]>=1000)
{
puts("-1");
return 0;
}
exsit[y] = true;
dl.push(y);
}
}
}
}
printf("%d
",dis[t]);
return 0;
}