Intervals
| Time Limit: 2000MS |
|
Memory Limit: 65536K |
| Total Submissions: 15733 |
|
Accepted: 5871 |
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 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
The first line of the input contains an integer n (1 <= n <= 50000) -- 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 <= 50000 and 1 <= ci <= bi - ai+1.
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
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
Sample Output
6
這題最多可能有5w的點，但是給的邊數有5w
而且要注意的是 對每個區間[i-1,i]都有>=0 <=1的條件
如果直接建圖的話，邊數可能有15w
所以時間上bellman_ford 可能很難承受
所有要優化
對于那些默認的條件，顯然我們可以不用把這些邊加進去，
在每次判斷時候，判斷一邊即可
對于bellman_ford 還有優化是，如果一次循環中沒有修改任何值，則說明bellman_ford已經得到解了，
沒必要繼續執行了 直接推出就行了
目標是求dist[mx]-dist[mn]
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cmath>
using namespace std;
#define inf 0x7ffffff
#define max 50004
struct node
{
int u,v,w;
}edge[max];
int n,dist[max],mn,mx;
void init()
{
int i;
for(i=0;i<max;i++) dist[i]=0;
mx=1;mn=inf;
}
void bellman_ford()
{
int k,t;
bool flag=true;
while(flag)
{
flag=false;
for(k=0;k<n;k++)
{
t=dist[edge[k].u]+edge[k].w;
if (dist[edge[k].v]>t)
{
dist[edge[k].v]=t;
flag=true;
}
}
for(k=mn;k<mx;k++)
{
t=dist[k-1]+1;
if (dist[k]>t)
{
dist[k]=t;
flag=true;
}
}
for(k=mn;k<mx;k++)
{
if (dist[k-1]>dist[k])
{
dist[k-1]=dist[k];
flag=true;
}
}
}
}
int main()
{
int i,u,v,w;
while (scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
edge[i].u=v;
edge[i].v=u-1;
edge[i].w=-w;
if (u<mn)
{
mn=u;
}
if (v>mx)
{
mx=v;
}
}
bellman_ford();
printf("%d\n",dist[mx]-dist[mn-1]);
}
return 0;
}