题目描述

一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

写一个程序完成以下工作：

输入输出格式

输入格式：

第一行包含数据N，区域的个数(0<N≤30000)；

第二行包含H，房子的数目(0<H≤5000)；

下面的H行描述居民们的需要：B E T，0<B≤E≤30000，T≤E-B+1。

输出格式：

输出文件只有一行写有树的数目

输入输出样例

输入样例#1：

输出样例#1：

一道变式的差分约束，每一个点代表该点编号到之前种了多少棵树。然后根据题意得到以下公式：num[E]-num[B-1]>=t。另外，本题有隐藏条件。首先，种树棵数必须是正的，那么对于任意K(0<K<=n)：满足条件num[K]>=num[K-1]。其次因为每个格子只能种一棵树，那么num[K]-num[K-1]<=1。所以我们再将上述条件移项得到以下三个式子：

num[E]-t>=num[B-1]

num[K]+0>=num[K-1]

num[K-1]+1>=num[K]

惊不惊喜？意不意外？这不就是道正正宗宗的差分约束模板吗？另外由于题目说明了一定有解，那么我们就可以愉快的建一个图跑一个SPFA再加个优化一波带走了呀~

不过别着急，这个代码有一些小技巧。我们知道差分约束是要每一个点都要SPFA一遍，但是那样很难写，并且效率低下。我们可以这样写：把N+1作为超级原点，向每一个点连上一条为0的边 num[N+1]>=num[i](0<=i<=n)，这样，N+1定义为了无穷大，那么对差分约束是没有影响的。答案即为num[N]-num[0]

下面是一段代码:

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 5e4 + 10;
const int maxm = 5e5 + 10;
struct edge {
	int v, w, next;
}e[maxm];
int head[maxn];
int cnt, n, m;
int dis[maxn];
bool vis[maxn];

void adde(const int &u, const int &v, const int &w) {
	e[cnt] = (edge) {v, w, head[u]};
	head[u] = cnt++;
}

void SPFA(int u) {
	deque<int > q;
	q.push_back(u);
	vis[u] = 1, dis[u] = 0;
	while(!q.empty()) {
		int now = q.front();
		q.pop_front(), vis[now] = 0;
		for(int i = head[now]; i != -1; i = e[i].next) {
			int v = e[i].v;
			if(dis[v] > dis[now] + e[i].w) {
				dis[v] = dis[now] + e[i].w;
				if(vis[v]) continue;
				vis[v] = 1;
				if(!q.empty() && dis[v] <= dis[q.front()]) 
					q.push_front(v);
				else q.push_back(v);
			}
		}
	}
}

void getans() {
	memset(dis, 0x3f, sizeof(dis));
	SPFA(n + 1);
	printf("%d", dis[n] - dis[0]);
}

int main() {
	memset(head, -1, sizeof(head));
	scanf("%d%d", &n, &m);
	for(int i = 0; i <= n; i++) {
		adde(n + 1, i, 0);
	}
	for(int i = 1; i <= n; i++) {
		adde(i-1, i, 1);
		adde(i, i-1, 0);
	}
	for(int i = 1; i <= m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		adde(v, u-1, -w);
	}
	getans();
	return 0;
}

Rockdu's Blog