图论--差分约束--POJ 1201 Intervals
图论--差分约束--POJ 1201 Intervals
Intervals Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 30971 Accepted: 11990 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
这个题我看了很久都不懂得怎么建图。先粘个代码吧！
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define inf 99999
#define maxx 50005
struct edge
{
int u,v,w;
}edge[maxx];
int n;
int dist[maxx];
int l;//左端点的最小值
int r;//右端点的最大值
void bellman_ford()
{
int flag=1,t;
while(flag)
{
flag=0;
for(int i=1;i<=n;i++)
{
t=dist[edge[i].u]+edge[i].w;
if(dist[edge[i].v]>t)
{
dist[edge[i].v]=t;
flag=1;
}
}
for(int i=r;i>l;i--)
{
t=dist[i-1]+1;
if(dist[i]>t)
{
dist[i]=t;flag=1;
}
}
for(int i=r;i>l;i--)
{
t=dist[i];
if(dist[i-1]>t)
{
dist[i-1]=t;
flag=1;
}
}
}
}
int main()
{
scanf("%d",&n);
r=1,l=inf;
int a,b,c;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a,&b,&c);
edge[i].u=b,edge[i].v=a-1,edge[i].w=-c;
if(a<l) l=a;
if(b>r) r=b;
dist[i]=0;
}
bellman_ford();
printf("%d\n",dist[r]-dist[l-1]);
return 0;
}