POJ1201-Intervals(差动限制)

Intervals

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 20786		Accepted: 7866

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

Sample Output

Source

Southwestern Europe 2002

一道典型的差分约束：

题目意思：

给你m个区间。每一个区间至少要取c个数

问最少取多少个数

解法:

用X(i) 表示前i个数中取了多少个数

对于每一个区间的约束建立下列不等不等式：

X(a) - X(b+1) <= -c

除此之外还有补充另外的边

X(i+1)-X(i) <= 1

要求的是

X(sink) - X(src) >= d (d即为所求)

即

X(src)-X(sink) <= -d

求sink到src的最短路径

SPFA搞定

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

using namespace std;

const int maxn = 50000+10000;

const int INF = 1e9;

int n;

int src,sink;

bool inQue[maxn];

int dist[maxn];

queue<int>que;

struct edge{

    int to,next,w;

    edge(int to,int next,int w):to(to),next(next),w(w){}

};

int head[maxn];

vector<edge> e;

void addedge(int from,int to,int w){

    e.push_back(edge(to,head[from],w));

    head[from] = e.size()-1;

}

void spfa(){

    for(int i = src; i <= sink; i++){

        inQue[i] = 0;

        dist[i] = INF;

    }

    inQue[sink] = 1;

    que.push(sink);

    dist[sink] = 0;

    while(!que.empty()){

        int u = que.front();

        que.pop();

        inQue[u] = 0;

        for(int i = head[u]; i != -1; i = e[i].next){

            if(dist[e[i].to] > dist[u]+e[i].w){

                dist[e[i].to] = dist[u]+e[i].w;

                if(!inQue[e[i].to]){

                    inQue[e[i].to] = 1;

                    que.push(e[i].to);

                }

            }

        }

    }

}

int main(){

    int m;

    freopen("in","r",stdin);

    while(~scanf("%d",&m)){

        e.clear();

        src = maxn,sink = -1;

        memset(head,-1,sizeof head);

        while(m--){

            int a,b,c;

            scanf("%d%d%d",&a,&b,&c);

            ++b;

            src = min(src,a);

            sink = max(sink,b);

            addedge(b,a,-c);

        }

        for(int i = src; i < sink; i++){

            addedge(i+1,i,0);

            addedge(i,i+1,1);

        }

        spfa();

        cout<<-dist[src]<<endl;

    }

    return 0;

}

秒客网

POJ1201-Intervals(差动限制)

相关文章