本文主要是介绍poj 1201 intervals，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链
Description
Write a program that:
reads the number of intervals, their end points and integers c1, ..., cn from the standard input,
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n,
writes the answer to the standard output.
Input
Output
Sample Input
5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1
Sample Output
6题目描述：
给定n割整数区间【ai,bi】和n个整数c1,c2,c3,,,,,cn 编程实现3点
（1） 以标准输入方式读入闭区间的个数，每个区间的端点和整数c1,c2,c3,,
(2)求一个最小的整数集合Z，满足|Z交[ai,bi]|>=ci,即Z里面的数中范围在闭区间【ai,bi】的个数不小于ci个，i=1,2,,,n
(3)以标准输出方式输出答案
基本思路： 《图论算法理论-实现与应用》p205,里面的解析更加详细一点
主要运用的是查分约束的思想，其中有两个是根据实际情况的两个约束条件：（s[i]表示在区间0-【i】内的个数）s[i]-s[i-1]<=1意思是在某个端点上的点的个数，其当然是<=1的；s[i]-s[i-1]>=0表示在端点处至少有0个点
在集合[ai,bi]中,s[bi]-s[ai-1]>=ci =>> s[ai-1]-s[bi]<=-ci;
注意本题直接用bellman的算法会超时，需要优化一下，见注释
利用以上约束条件建图，求解
<pre name="code" class="cpp">#include <iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define MAX 50005
#define inf 0x3f3f3f3fusing namespace std;struct node
{int u,v,w;//边：起点，终点，权值
}A[MAX];int dist[MAX];//源点到各个顶点的最短路径
int mx,mi;//区间端点的最大值和最小值
int ant;
int n;//区间的个数void init()
{mi=inf;mx=0;for(int i=0;i<n;i++){dist[i]=0;
//出事化为0，因为si-smx<=0,所以源点到各个顶点的最短距离肯定小于0的}
}
void bellman()
{int f=1;//标志变量，为提前结束bellman算法的标志变量
//只要末次循环过程中，没能改变源点到各个顶点的最短距离，则可以提前结束while(f){f=0;for(int j=0;j<n;j++){int u=A[j].u;int v=A[j].v;if(dist[v]>dist[u]+A[j].w){dist[v]=dist[u]+A[j].w;f=1;}}///s[i]<=s[i-1]+1for(int j=mi;j<=mx;j++)//进一步修改s[i]{if(dist[j]>dist[j-1]+1){dist[j]=dist[j-1]+1;f=1;}}///s[i-1]<=s[i]for(int j=mi;j<=mx;j++)//进一步修改s[i-1]{if(dist[j-1]>dist[j]){dist[j-1]=dist[j];f=1;}}}
}
int main()
{while(~scanf("%d",&n)){init();for(int i=0,u,v,w;i<n;i++){scanf("%d%d%d",&u,&v,&w);A[i].u=v;A[i].v=u-1;A[i].w=-w;if(mi>u)mi=u;if(mx<v)mx=v;}bellman();printf("%d\n",dist[mx]-dist[mi-1]);}return 0;
}这篇关于poj 1201 intervals的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
