图论--差分约束--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;

}

巴特西

图论--差分约束--POJ 1201 Intervals

最新文章

热门文章