当前位置:编程学习 > C/C++ >>

POJ 1201 Intervals

Intervals
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 18456 Accepted: 6919
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
Source
Southwestern Europe 2002
     考差分约束,自我感觉是这类问题是找不等式关系,然后想方法建图,然后用一遍spfa就可以了
 初步接触差分约束
[cpp] 
#include <stdio.h>  
#include <string.h>  
#include <math.h>  
struct num  
{  
    int end,val,next;  
}a[1000000];  
int b[50100];  
int d[50100],queue[1000000];  
int status[50100];  
int INF=0x7fffff;  
int main()  
{  
    int spfa(int sta,int end);  
    int i,j,n,m,s,t;  
    int x,y,val,max,min;  
    while(scanf("%d",&n)!=EOF)  
    {  
        memset(b,-1,sizeof(b));  
        max=-1; min=INF;  
        for(i=0,j=0;i<=n-1;i++)  
        {  
            scanf("%d %d %d",&x,&y,&val);  
            x++; y++;  
            if(x-1<min)  
            {  
                min=x-1;  
            }  
            if(y>max)  
            {  
                max=y;  
            }  
            a[j].end= y;  
            a[j].val=val;  
            a[j].next=b[x-1];  
            b[x-1]=j; j++;  
        }  
        for(i=min+1;i<=max;i++)  
        {  
            a[j].end=i;  
            a[j].val=0;  
            a[j].next=b[i-1];  
            b[i-1]=j; j++;  
            a[j].end=i-1;  
            a[j].val=-1;  
            a[j].next=b[i];  
            b[i]=j; j++;  
        }  
        t=spfa(min,max);  
        printf("%d\n",t);  
    }  
    return 0;  
}  
int spfa(int sta,int end)  
{  
    int i,j,top,base,x,xend,y;  
    for(i=sta;i<=end;i++)  
    {  
        d[i]=-1*INF;  
    }  
    top=base=0;  
    queue[top++]=sta;  
    d[sta]=0;  
    memset(status,0,sizeof(status));  
    status[sta]=1;  
    while(base<top)  
    {  
        x=queue[base++];  
        status[x]=0;  
        for(j=b[x];j!=-1;j=a[j].next)  
        {  
            y=a[j].end;  
            if(d[y]<(d[x]+a[j].val))  
            {  
                d[y]=d[x]+a[j].val;  
                if(!status[y])  
                {  
                    queue[top++]=y;  
                }  
            }  
        }  
    }  
    return (d[end]);  
}  
 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,