Intervals |
| Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
| Total Submission(s): 52 Accepted Submission(s): 32 |
|
Problem Description
You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.
Write a program that: > reads the number of intervals, their endpoints 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
The first line of the input contains an integer n (1 <= n <= 50 000) - the number of intervals. The following n lines describe the intervals. The i+1-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50 000 and 1 <= ci <= bi - ai + 1.
Process to the end of file. |
|
Output
The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i = 1, 2, ..., n.
|
|
Sample Input
5 |
|
Sample Output
6 |
|
Author
1384
|
|
Recommend
Eddy
|
/*
题意：给n个条件 ai bi ci 表示在[ai,bi]最少取ci个数，问你最少取多少点，才能满足这些条件 初步思路：差分约束问题，差分约束问题，实际上就是利用图论的知识计算不等式，每个不等式建立一条边，然后利用最短路
跑一下
*/
#include<bits/stdc++.h>
using namespace std;
int u,v,w,n;
/*****************************************************spaf模板*****************************************************/
template<int N,int M>
struct Graph
{
int top;
struct Vertex{
int head;
}V[N];
struct Edge{
int v,next;
int w;
}E[M];
void init(){
memset(V,-,sizeof(V));
top = ;
}
void add_edge(int u,int v,int w){
E[top].v = v;
E[top].w = w;
E[top].next = V[u].head;
V[u].head = top++;
}
}; Graph<,> g; const int N = 5e4 + ; int d[N];//从某一点到i的最短路
int inqCnt[N]; bool inq[N];//标记走过的点 bool spfa(int s,int n)
{
memset(inqCnt,,sizeof(inqCnt));
memset(inq,false,sizeof(inq));
memset(d,-,sizeof(d));
queue<int> Q;
Q.push(s);//将起点装进队列中
inq[s] = true;
d[s] = ;
while(!Q.empty())
{
int u = Q.front();
for(int i=g.V[u].head;~i;i=g.E[i].next)//遍历所有这个点相邻的点
{
int v = g.E[i].v;
int w = g.E[i].w;
if(d[u]+w>d[v])//进行放缩
{
d[v] = d[u] + w;
if(!inq[v])//如果这个点没有遍历过
{
Q.push(v);
inq[v] = true;
if(++inqCnt[v] > n)
return true;
}
}
}
Q.pop();//将这个点出栈
inq[u] = false;
}
return false;
}
/*****************************************************spaf模板*****************************************************/
int main(){
// freopen("in.txt","r",stdin);
while(scanf("%d",&n)!=EOF){
g.init();
int L=,R=;
for(int i=;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
++u,++v;
//找出左右两个边界
L=min(L,u);
R=max(R,v);
g.add_edge(u-,v,w);
}
for(int i=L;i<=R;i++) {
g.add_edge(i-,i,);
g.add_edge(i,i-,-);
}
spfa(L-,R-L+);
printf("%d\n",d[R]); }
return ;
}