首页 > 代码库 > poj1201 Intervals，差分约束问题，spfa

poj1201 Intervals，差分约束问题，spfa

2024-07-22 06:54:32   222人阅读

题目大意：
有一个序列，题目用n个整数组合 [ai,bi,ci]来描述它，[ai，bi，ci]表示在该序列中处于[ai，bi]这个区间的整数至少有ci个。如果存在这样的序列，请求出满足题目要求的最短的序列长度是多少。如果不存在则输出 -1。
输入：第一行包括一个整数n，表示区间个数，以下n行每行描述这些区间，第i+1行三个整数ai，bi，ci，由空格隔开，其中0<=ai<=bi<=50000 而且 1<=ci<=bi-ai+1。

输出：一行，输出满足要求的序列的长度的最小值。


sum[i] = sigma[1,i]

不等式：

sum[b[i]] - sum[a[i]-1] >= ci

sum[i+1] - sum[i] >= 0

sum[i] - sum[i+1] >= -1


对于 

d[v] >= d[u] + w，可以转化为求最长路（u->v连边权值为w）来求d[i]的最小值


/*sum(i) =  sigma[1..i]
 *sum(bi) - sum(ai) >= ci
 *sum(i) - sum(i-1) >= 0
 *sum(i-1) - sum(i) >= -1
 *d(v) >= d(u) + w , 求最长路 
 * */
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
const int maxn = 50000 + 100;
const int maxm = 500000 + 100;
const int INF = 1e8;

int head[maxn], tot;

struct Edge{
	int to, w, next;
}edge[maxm];

void init(){
	tot = 0;
	memset(head, -1, sizeof head );
}

void addedge(int u, int v, int w){
	edge[tot].to = v;
	edge[tot].w = w;
	edge[tot].next = head[u];
	head[u] = tot++;
}

int d[maxn];
bool vis[maxn];
queue<int> q;
int Mn, Mx;

int spfa(){
	int s = Mn;
	while(!q.empty()) q.pop(); 
	for(int i=Mn; i<=Mx; ++i) d[i] = -INF;
	memset(vis, false, sizeof vis );
	q.push(s); d[s] = 0; vis[s] = true;
	while(!q.empty()){
		int u = q.front(); q.pop();
		vis[u] = false;
		for(int i=head[u]; ~i; i=edge[i].next){
			int &v = edge[i].to;
			int &w = edge[i].w;
			if(d[v] < d[u] + w){
				d[v] = d[u] + w;
				if(!vis[v]){
					vis[v] = true;
					q.push(v);
				}
			}
		}
	}
	return d[Mx];
}

int main()
{
	int n, u, v, w;
	init();
	scanf("%d", &n);
	Mn = INF, Mx = -INF;
	for(int i=0; i<n; ++i){
		scanf("%d%d%d", &u, &v, &w);
		addedge(u, v+1, w);
		Mn = min(Mn, u);
		Mx = max(Mx, v+1);
	}
	for(int i=Mn; i<Mx; ++i){
		addedge(i, i+1, 0);
		addedge(i+1, i, -1);
	}
	printf("%d\n", spfa());
	return 0;
}


poj1201 Intervals，差分约束问题，spfa


联系
我们