本文共 2376 字，大约阅读时间需要 7 分钟。

原题链接：

一：原题内容

Description

Input

Output

Sample Input

53 7 38 10 36 8 11 3 110 11 1

Sample Output

6

二：分析理解

题目说[ai, bi]区间内和点集Z至少有ci个共同元素，那也就是说如果我用Si表示区间[0,i]区间内至少有多少个元素的话，那么Sbi - Sai >= ci,这样我们就构造出来了一系列边，权值为ci，但是这远远不够，因为有很多点依然没有相连接起来（也就是从起点可能根本就还没有到终点的路线）,此时，我们再看看Si的定义，也不难写出0<=Si - Si-1<=1的限制条件，虽然看上去是没有什么意义的条件，但是如果你也把它构造出一系列的边的话，这样从起点到终点的最短路也就顺理成章的出现了。

三：AC代码

#include
   
        #include
    
       #include
     
        using namespace std;struct Edge{	int v;	int w;	int next;};Edge edge[50005 * 3];int head[50005];int dis[50005];bool visited[50005];int sta[50005];int n;int a, b, c;int num = 0;void AddEdge(int u, int v, int w){	edge[num].v = v;	edge[num].w = w;	edge[num].next = head[u];	head[u] = num++;}void Spfa(int s){	fill(dis, dis + 50005, -99999999);	int top = 1;	dis[s] = 0;	visited[s] = 1;	sta[top] = s;	while (top)	{		int u = sta[top--];		visited[u] = 0;		for (int i = head[u]; i != -1; i = edge[i].next)		{			int v = edge[i].v;			if (dis[v] < dis[u] + edge[i].w)			{				dis[v] = dis[u] + edge[i].w;				if (!visited[v])				{					sta[++top] = v;					visited[v] = 1;				}			}		}	}}int main(){	scanf("%d", &n);	memset(head, -1, sizeof(head));	int maxx = -1;	int minn = 99999999;	for (int i = 0; i < n; i++)	{		scanf("%d%d%d", &a, &b, &c);		AddEdge(a, b + 1, c);		minn = min(a, minn);		maxx = max(b + 1, maxx);	}	for (int i = minn; i < maxx; i++)	{		AddEdge(i, i + 1, 0);		AddEdge(i + 1, i, -1);	}	Spfa(minn);	printf("%d\n", dis[maxx]);	return 0;}
     
    
   

转载地址：https://blog.csdn.net/LaoJiu_/article/details/51034976 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！