首页 > 代码库 > POJ1201-Intervals(差分约束)

POJ1201-Intervals(差分约束)

2024-07-09 02:59:03   220人阅读

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

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

Sample Output

6

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 = http://www.mamicode.com/maxn,sink = -1;>


联系
我们